제7 장 (상) 재 귀, DFS, 가지치기, 역 추적 문제
22331 단어 겨울방학 알고리즘
귀속 문제
1. 재 귀 교체: (재 귀 는 교체 로 바 꿀 수 있 고 재 귀 는 위 에서 아래로 거꾸로 생각 하 는 것 이다. 교 체 는 아래 에서 위로 한 걸음 씩 변 수 를 업데이트 하 는 것 이다. 사실은 재 귀 와 교체 가 더 좋 고 그 가 차지 하 는 공간 이 적 기 때문에 재 귀 처럼 창고 의 구 조 를 사용 하지 않 아 도 큰 곳 을 열 어야 한다)(그러나 재 귀 는 더욱 강 한 표 현 력 을 가지 고 몇 마디 코드 로 복잡 한 관 계 를 표현 하 며 교체 로 바 꾸 려 면 많은 글 을 써 야 한다) (재 귀 문 제 는 수치 형 과 비 수치 형 으로 나 뉜 다)
계단 은 n 단계 가 있 습 니 다. 아 이 는 한 번 에 1 * 65340 ° 2 * 65340 ° 3 단계 에 올 라 갈 수 있 습 니 다. 아이 가 몇 가지 올 라 가 는 방식 이 넘 치 는 것 을 방지 하기 위해 결 과 를 mod 1000000007 로 계산 하 십시오.
class Test48{
static int mod = 1000000007; // Ｉｎｔ ，ｊａｖａ int :-2147483648 2147483648（１０ ）
public static void main(String[] args) {
}
static long recursion(int n){
if(n<0) return 0;
if(n==0 || n==1) return 1;
if(n==2) return 2;
return recursion(n-1)%mod+recursion(n-2)%mod+recursion(n-3)%mod;
}
static int recursion2(int n){
if(n<0) return 0;
if(n==0||n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
int x1 = 1;
int x2 = 2;
int x3 =4;
for(int i=4;i<=n;i++){
int x_1 = x1;
x1 = x2%mod;
x2 = x3%mod;
x3 = ((x1+x2)%mod+x_1)%mod;
}
return x3;
}
}
2. 로봇 의 그리드 문제:
x 가 하나 있어 요.×Y 의 격자, 한 로봇 이 점 을 걷 고 오른쪽 이나 아래로 만 내 려 갈 수 있 습 니 다. 왼쪽 상단 에서 오른쪽 아래 까지 로봇 에 게 몇 가지 알고리즘 이 있 는 지 물 어보 고 x + y 는 12 보다 작 아야 합 니 다.
관건 은 f (x, y) = f (x, y - 1) + f (x - 1, y) 이다.
역시 두 가지 문법 이 있어 요.
class Test48{
public static void main(String[] args) {
}
//
static int solve(int x,int y){
if(x==1 || y==1){
return 1;
}
return solve(x-1,y)+solve(x,y-1);
}
// （ ， , ， ， ）
static int solve2(int m,int n){
int [][]state = new int[m+1][n+1];// ， ０
for(int i=1;i<=n;i++){
state[1][i] = 1;
}
for(int i=1;i<=m;i++){
state[i][1]= 1;
}
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
state[i][j] = state[i][j-1]+state[i][j-1];
}
}
return state[m][n];
}
}
3. 동전 은 문 제 를 나타 낸다.
8 가지 액면가 동전 1, 2, 5, 10, 20, 50, 100, 200 주어진 수치 n
사고방식: 순환 중 에 돌아 가면 모든 작은 사장 은 최대 액면가 의 화폐 가 몇 장 을 사용 하 는 지 만 결정 한다.
그리고 남 은 돈 은 다음 에 맡 기 겠 습 니 다.
여기 가 로봇 보다 복잡 한 곳 은 한 곳 이 아니 라 이 물건 을 원 하 는 것 이다. 아니면 내 가 두 개 를 원 하거나 내 가 세 개 를 원 하 는 것 이다.
class Test48{
public static void main(String[] args) {
}
static int countways(int n){
if(n<=0) return 0;
return countwayscore(n,new int[]{1,5,10,25},3);//３ ０～３
}
static int countwayscore(int n,int[] coins,int cur){
if(cur==0) return 1;
int res =0;
for(int i=0;i*coins[cur]<=n;i++){
int shengyu = n-i*coins[cur];
res+=countwayscore(shengyu,coins,cur-1);
}
return res;
}
}
4. 귀속 문제 의 비수 치 문제 의 해법
불법 괄호 문제: n 입력, n 대괄호 의 모든 유효한 조합 인쇄
import java.util.HashSet;
import java.util.Set;
class Test48{
public static void main(String[] args) {
Set par= parenthesis(3);
System.out.println(par);
}
static Set parenthesis(int n){
Set s_n = new HashSet<>();
if(n==1){
s_n.add("()");
return s_n;
}
Set s_n_1 = parenthesis(n-1);
for(String ex:s_n_1){
s_n.add("()"+ex);
s_n.add(ex+"()");
s_n.add("("+ex+")");
}
return s_n;
}
//
static Set parenthesis2(int n){
Set res = new HashSet<>();
res.add("()");
if(n==1){
return res;
}
for(int i=2;i<=n;i++){
Set res_new = new HashSet<>();
for(String e:res){
res_new.add(e+"()");
res_new.add("()"+e);
res_new.add("("+e+")");
}
res = res_new;
}
return res;
}
}
5. 비 빈자리 집합
public class _9_4 {
public static void main(String[] args) {
int[] A = {1, 2, 3};
_9_4 obj = new _9_4 ();
Set> subsets3 = obj.getSubsets3(A, A.length);
System.out.println(subsets3);
Set> subsets2 = obj.getSubsets2(A, A.length);
System.out.println(subsets2);
ArrayList> subsets = obj.getSubsets(A, A.length);
System.out.println(subsets);
}
/**
* , ,
* @param A
* @param n
* @return
*/
public ArrayList> getSubsets(int[] A, int n) {
Arrays.sort(A);//
ArrayList> res = new ArrayList<>();//
for (int i = Case11_NExponent.ex(2, n) - 1; i > 0; i--) {// -1
ArrayList s = new ArrayList<>();// i
for (int j = n - 1; j >= 0; j--) {// 1, ,
if (((i >> j) & 1) == 1) {
s.add(A[j]);
}
}
res.add(s);
}
return res;
}
/* */
public Set> getSubsets2(int[] A, int n) {
Set> res = new HashSet<>();
res.add(new HashSet<>());//
//
for (int i = 0; i < n; i++) {
Set> res_new = new HashSet<>();// ,,zhe ge da ji he li mian jia wan dongxi hou zai tihuan diao yuanlai de jihe
res_new.addAll(res);//
// ,
for (Set e : res) {
Set clone = (Set) ((HashSet) e).clone();
clone.add(A[i]);//
res_new.add(clone);//
}
res = res_new;
}
return res;
}
public Set> getSubsets3(int[] A, int n) {
// Arrays.sort(A);
return getSubsets3Core(A, n, n - 1);
}
private Set> getSubsets3Core(int[] A, int n, int cur) {
Set> newSet = new HashSet<>();
if (cur == 0) {//
Set nil = new HashSet<>();//
Set first = new HashSet<>();//
first.add(A[0]);
newSet.add(nil);
newSet.add(first);
return newSet;
}
Set> oldSet = getSubsets3Core(A, n, cur - 1);//dao zhe chu li de
for (Set set : oldSet) {
// ,cur ,
newSet.add(set);//
Set clone = (Set) ((HashSet) set).clone();
clone.add(A[cur]);//
newSet.add(clone);
}
return newSet;
}
}
7. 전체 배열 문제:
질문
(집합 적 인 사고방식 으로 빈 칸 에 꽂 기)
import java.util.ArrayList;
class Test48{
public static void main(String[] args) {
ArrayList res = getpermutation("abcd");
System.out.println( res);
}
static ArrayList getpermutation(String A){
int n = A.length();
ArrayList res = new ArrayList<>();
res.add(A.charAt(0)+""); // ，
for (int i=1;i res_new = new ArrayList<>();
char c= A.charAt(i);
for(String str:res){
String newstr = c+str;
res_new.add(newstr);
newstr = str + c;//
res_new.add(newstr);
for(int j =1;j 전체 배열 문제 의 귀속
import java.util.ArrayList;
class Test48{
public static void main(String[] args) {
ArrayList res = getpermutation("abcd");
System.out.println( res);
}
static ArrayList getpermutation(String A){
int n = A.length();
ArrayList res = new ArrayList<>();
res.add(A.charAt(0)+""); // ，
for (int i=1;i res_new = new ArrayList<>();
char c= A.charAt(i);
for(String str:res){
String newstr = c+str;
res_new.add(newstr);
newstr = str + c;//
res_new.add(newstr);
for(int j =1;j 전체 배열 의 역 추적 알고리즘
난점: 다 중 재 귀, 역 추적 (원점 으로 회복),
import java.util.ArrayList;
import java.util.Arrays;
class Test48{
public static void main(String[] args) {
ArrayList res = getpermutation("12345");
System.out.println(res);
}
static ArrayList res = new ArrayList<>();
static ArrayList getpermutation(String A){
char[] arr= A.toCharArray();
Arrays.sort(arr);
getpermutationcore(arr,0);
return res;
}
static void getpermutationcore(char[] arr,int k){
if(k==arr.length){
res.add(new String(arr));
}
for(int i=k;i 전체 배열 의 접두사 스 캔 법
class Test48{
public static void main(String[] args) {
String s = "123";
permutation("",s.toCharArray());
}
static int count =0;
static int k= 3;
static void permutation(String prefix,char[] arr){
if(prefix.length() == arr.length){
count++;
if(count==k){
System.out.println("----------"+prefix);
}
}
for(int i=0;i8. 폐쇄 식 예
재 귀 중 폐쇄 식 문 제 는 수학 귀납법 으로 직접 답 을 얻 을 수 있 는 문제 라 는 뜻 이다.
예 를 들 어 한 노 타 문 제 는 예 를 들 면 2 ^ n - 1 임 을 알 수 있다.
피 보 나치 수열 n 항 도 공식, 행렬 [1, 1] 을 그 행렬 로 만 드 는 알고리즘 을 사용 할 수 있다.
계단 오 르 기 문제
상술 한 문 제 는 규칙 을 찾 는 것 이 중요 하 다.
아래 심층 검색 시작!
DFS: 본질 은 무엇 입 니까? 바로 계속 내 려 가 는 방법 입 니 다. 내 려 갈 수 없 으 면 취소 버튼 을 누 르 고 다른 방법 을 시도 하 는 것 입 니 다. 이런 방법 들 은 처음에 평행 관계 입 니 다.dfs 는 자신 이 자신 을 호출 하 는 과정 이 고 bfs 는 그림 의 문제 입 니 다. 지금 여기 서 주의해 야 할 시작 방향 은 반드시 줄 의 가 열 을 큰 순환 에 넣 지 않 아 도 된다 는 것 입 니 다. 그들의 변 화 는 전체 조건 내부 의 다음 상태 일 수 있 습 니 다.
9. dfs 예제:
당신 은 반드시 "게임" 을 들 어 본 적 이 있 습 니 다. 아래 그림 에서 보 듯 이 유 저 는 9 에 근거 해 야 합 니 다.×9 판 의 이미 알 고 있 는 숫자 는 모든 빈 칸 의 숫자 를 추리 하여 각 줄, 각 열, 같은 색 의 구 궁 안의 숫자 는 1 - 9 를 포함 하여 중복 되 지 않 습 니 다. 수 독 의 답 은 모두 유일한 것 이기 때문에 여러 개의 풀이 도 무 해 라 고 합 니 다. 이 그림 의 숫자 는 핀란드 수학자 들 이 3 개 월 동안 설계 한 어 려 운 문제 라 고 합 니 다. 그러나 컴퓨터 로 편집 할 줄 압 니 다.이 문제 의 요 구 는 수 독 문 제 를 입력 하 는 것 입 니 다. 프로그램 출력 수 독 의 유일한 풀이 입 니 다. 우 리 는 이미 알 고 있 는 모든 데이터 의 형식 이 합 법 적 이 고 문 제 는 유일한 풀이 가 있 음 을 보장 합 니 다. 형식 요구, 9 줄 입력, 줄 당 9 개의 숫자, 0 대 표 는 알 수 없 으 며, 기타 숫자 는 이미 알 고 있 습 니 다. 9 줄 을 출력 하고 줄 당 9 개의 숫자 는 수 독 해 를 표시 합 니 다. 지 는 것 입 니 다.입력:
005300000 800000020 070010500 400005300 010070006 003200080 060500009 004000030 000009700
프로그램 출력:
145327698 839654127 672918543 496185372 218473956 753296481 367542819 984761235 521839764
public class Dfs1_ {
public static void main(String[] args) {
// System.out.println((char)('0'+1));
Scanner sc = new Scanner(System.in);
char[][] table = new char[9][];
for (int i = 0; i < 9; i++) {
table[i] = sc.nextLine().toCharArray();
}
dfs(table, 0, 0);
}
private static void dfs(char[][] table, int x, int y) {
if (x == 9) {
print(table);
System.exit(0);
}
if (table[x][y] == '0') {//
for (int k = 1; k < 10; k++) {
if (check(table, x, y, k)) {
// f = false;
table[x][y] = (char) ('0' + k);
dfs(table, x + (y + 1) / 9, (y + 1) % 9); ，ｙ ９ ，ｘ＋ ，ｙ ， ９ １
}
}
table[x][y] = '0';//
} else {
dfs(table, x + (y + 1) / 9, (y + 1) % 9);//
}
}
private static void print(char[][] table) {
for (int i = 0; i < 9; i++) {
System.out.println(new String(table[i]));
}
}
private static boolean check(char[][] table, int i, int j, int k) {
//
for (int l = 0; l < 9; l++) {
if (table[i][l] == (char) ('0' + k)) return false;
if (table[l][j] == (char) ('0' + k)) return false;
}
//
for (int l = (i / 3) * 3; l < (i / 3 + 1) * 3; l++) {
for (int m = (j / 3) * 3; m < (j / 3 + 1) * 3; m++) {
if (table[l][m] == (char) ('0' + k)) return false;
}
}
return true;
}
}
10. 부분 과
주어진 정수 서열 a1, a2,..., an, 그 중에서 몇 개의 수 를 선택 하여 그것들의 합 계 를 k 로 할 수 있 는 지 판단 합 니 다.
1≤n≤20
-10^8≤ai≤10^8
-10^8≤k≤10^8
샘플:
입력
n=4 a={1,2,4,7} k = 13 출력:
Yes (13 = 2 + 4 + 7)
사고: 이 문 제 는 처음에 하위 배열 로 할 수 있 고 모든 하위 배열 을 구 한 다음 에 볼 때 13 과 같 지 않다.
dfs 도 가능 합 니 다.
import java.util.ArrayList;
import java.util.Scanner;
class Main{
static int kk;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int k = sc.nextInt();//13
kk =k;
dfs(a,k,0,new ArrayList());
}
static void dfs(int[] a, int k, int cur,ArrayList ints){
if(k==0){
System.out.print("Yes("+kk+" = ");
int size = ints.size();
for(int i=0;i 11. 물웅덩이 수 (이 재 귀 는 거 슬러 올 라 갈 필요 가 없다)
N * M 크기 의 정원 이 있 습 니 다. 비가 온 후에 물이 고 였 습 니 다. 8 연 결 된 고인 물 은 연결 되 어 있 는 것 으로 여 겨 집 니 다. 정원 에 모두 몇 개의 웅덩이 가 있 는 지 요청 하 십시오.
*** *W* ***
제한 조건
N, M ≤ 100
샘플:
입력 N=10, M=12
정원 은 아래 그림 과 같다.
W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
출력
3
import java.util.Scanner;
public class Main {
private static int n;
private static int m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
char[][] a = new char[n][];
for (int i = 0; i < n; i++) {
a[i] = sc.next().toCharArray();
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 'W') {
dfs(a, i, j);//
cnt++;
}
}
}
System.out.println(cnt);
}
private static void dfs(char[][] a, int i, int j) {
a[i][j] = '.';
for (int k = -1; k < 2; k++) {//-1,0,1
for (int l = -1; l < 2; l++) {//-1,0,1
if (k == 0 && l == 0) continue;// ，，
if (i + k >= 0 && i + k <= n - 1 && j + l >= 0 && j + l <= m - 1) {//
if (a[i + k][j + l] == 'W')
dfs(a, i + k, j + l);
}
}
}
}
}
이 문제 관련:
제목: 마 이 클 이 스키 백 을 좋아 하 는 것 은 이상 하지 않다. 스키 를 타 는 것 은 확실히 자극 적 이기 때문이다. 그러나 속 도 를 얻 기 위해 서 는 미 끄 러 지 는 구역 이 아래로 기울 어야 한다. 그리고 언덕 밑 까지 미 끄 러 지면 다시 언덕 을 오 르 거나 승강기 가 태 워 줄 때 까지 기 다 려 야 한다. 마 이 클 은 한 구역 에서 가장 긴 미끄럼 을 타 는 것 을 알 고 싶다. 구역 은 2 차원 배열 에 의 해 제시 된다. 배열 의 모든 숫자 대표 점 의높이
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13. 12, 11, 109 한 사람 이 특정한 점 에서 상하 좌우 로 4 개의 점 중 하 나 를 미 끄 러 뜨 릴 수 있 고 높이 만 줄 일 수 있다. 위의 예 에서 미 끄 러 질 수 있 는 슬로프 는 24 - 17 - 16 - 1 이다. 물론 25 - 24 - 23 -... - 3 - 2 - 1 이 더 길다. 사실은 이것 이 가장 긴 것 이다.
import java.util.Scanner;
public class test {
static int r,c,sum=0;
static int[][]map;
static int[][] memo;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
r = sc.nextInt();
c = sc.nextInt();
map = new int[r][c];
memo = new int[r][c];
for(int i=0;i= 0 && i + k <= r - 1 && j + l >= 0 && j + l <=c - 1&&memo[i][j]>memo[i+k][j+l]){
len = Math.max(len,memo[i+k][j+l]+1);
}
}
}
memo[i][j] = len;
return memo[i][j];
}
} 이 코드 는 현재 옳지 않 습 니 다. 생각 이 옳 습 니 다. 발견 한 후에 코드 를 고 칠 것 입 니 다.
황후
유명한 n 황후 문 제 를 해결 하기 위해 알고리즘 을 설계 하 십시오. 여기 n 황후 문 제 는 n * n 의 바둑판 에 n 개의 바둑 알 을 놓 는 것 을 말 합 니 다. * 모든 줄 과 각 대각선 에 바둑 알 이 하나 밖 에 없 게 하여 배치 하 는 방법 수 를 구하 게 하 다.
int n 을 지정 하 였 습 니 다. 방법 수 를 되 돌려 주 십시오. n 이 15 보다 작 을 것 을 보증 합 니 다.
public class Dfs_4n {
static int n;
static int cnt;
static int[] rec;
public static void main(String[] args) {
n = 4;
rec = new int[4];
dfs(0);
System.out.println(cnt);
}
/**
*
* @param row
*/
private static void dfs(int row) {
if (row == n) {
cnt++;
return;
}
//
for (int col = 0; col < n; col++) {
boolean ok = true;
//
for (int i = 0; i < row; i++) {
if (rec[i] == col || i + rec[i] == row + col || rec[i] - i == col - row) {
ok = false;
break;
}
}
/*======= =======*/
//
if (ok) {
rec[row] = col; //
dfs(row + 1); //
// rec[row]=0; // ， ， ？
}
}
}
}
１３、 * 정수 n 을 입력 하고 1 - n 을 배열 하여 인접 한 두 수의 합 을 모두 소수 로 합 니 다. * 출력 할 때 정수 1 부터 시계 반대 방향 으로 배열 합 니 다. 같은 고 리 는 마침 출력 해 야 합 니 다. * n<=16 * * 입력: 6 * 출력: * 1 4 3 2 5 6 * 1 6 5 2 3 4 *
public class Dfs_5 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] r = new int[n];
r[0] = 1;
dfs(n, r, 1);
}
private static void dfs(int n, int[] r, int cur) {
if (cur == n && isP(r[0] + r[n - 1])) {// ,
print(r);
return;
}
for (int i = 2; i <= n; i++) {// cur
if (check(r, i, cur)) {//r i ,
r[cur] = i;// i cur ,
dfs(n, r, cur + 1);
r[cur] = 0;//
}
}
}
private static void print(int[] r) {
for (int i = 0; i < r.length; i++) {
System.out.print(r[i] + (i == r.length - 1 ? "" : " "));
}
System.out.println();
}
private static boolean check(int[] r, int i, int cur) {
for (int e : r) {
if (e == i || !isP(r[cur - 1] + i)) return false;
}
return true;
}
private static boolean isP(int k) {
for (int i = 2; i * i <= k; i++) {
if (k % i == 0) return false;
}
return true;
}
}
１４、
* 문제 설명: 한 문자열 에 두 개의 인접 한 중복 하위 문자열 이 포함 되 어 있다 면 쉬 운 문자열 이 라 고 부 르 고, 다른 문자열 은 어 려 운 문자열 이 라 고 부 릅 니 다. * 예 를 들 어 BB, ABCDACABCAB, ABCDABCD 는 모두 쉽다. A, AB, ABA, D, DC, ABDAB, CBABCBA 는 모두 어렵다.
정수 n, L 을 입력 하 십시오. 출력 은 앞의 L 글자 (대문자) 로 구 성 된 사전 순서 n 번 째 어 려 운 문자열 입 니 다. 예 를 들 어 L = 3 일 때 앞의 7 개의 어 려 운 문자열 은 다음 과 같다. A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA n. 4 로 지정 하면 ABAC 출력
public class Main{
public static void main(String[] args) {
int n = 10;
int l = 4;
dfs(l, n, "");
// isHard("0123020120",1);
}
static int count;
private static void dfs(int l, int n, String prefix) {
// prefix
for (char i = 'A'; i < 'A' + l; i++) {
if (isHard(prefix, i)) {// ,
String x = prefix + i;
System.out.println(x);
count++;//
if (count == n)
System.exit(0);
dfs(l, n, x);
}
}
}
/**
* prefix+i
* 1. ,
* 2.prefix ABACA i
* @param prefix
* @param i
* @return
*/
private static boolean isHard(String prefix, char i) {
int count = 0;//
for (int j = prefix.length() - 1; j >= 0; j -= 2) {
final String s1 = prefix.substring(j, j + count + 1);
final String s2 = prefix.substring(j + count + 1) + i;
if (s1.equals(s2))
return false;
count++;
}
return true;
}
}
우 리 는 여기에 들 어 오 는 방법 이 원래 어 려 운 문자열 이라는 것 을 고려 하여 위 와 같이 검색 상황 을 판단 할 필요 가 없다. 현재 추 가 된 문자 와 다른 문 자 를 조합 하여 인접 한 길이 의 문자열 과 비교 해 보면 같 는 지, 같 으 면 이 문 자 를 추가 한 후에 쉬 운 문자열 이 된다. 그러면 이것 은문 자 는 버 려 야 합 니 다.
여기 서 왜 그 어 려 운 꼬치 가 그렇게 count 를 절단 의 길이 로 판단 하 는 지 잘 알 아야 합 니 다. 매번 에 하 나 를 더 하면 j 는 시작 부분 이 고 대칭 여 부 를 판단 하 는 것 은 반드시 짝수 이기 때문에 한 번 에 2 를 줄 여야 합 니 다.
sunbstring ：
public String substring(int beginIndex)
public String substring(int beginIndex, int endIndex)
매개 변수
좋은 웹페이지 즐겨찾기
