[コケ]05-ブルトポス(NとM)

5785 ワード

CodingTest テキストリンク

再帰関数
1)手順
契約書に関する質問をN個引く
N!時間の複雑さ
N種類あれば何でもできるけどM個を選ぶ順番
2)選択
N種類の場合は選択に関連する
2^nの時間複雑度

NとM(1)

1からNまで自然数の中ですべて繰り返しないM個の数の列の問題を求めます
1<=M<=N<=8

貴:どこまで行けるか決めます.
->再帰関数を使用します.場所の変更と実行方法は同じです.

1からNまでの数字の1つ/1からNまでの数字の1つ.../Mまで繰り返す

1～Nの前の未使用の数

位置:関数のパラメータ.(第一、第二など、位置が重要)

前に使用する水道管を管理しなければならない.

<解答>

c[i]:iをtrue、falseとして使用しない

a[10]:数列を保存します.

go(index,n,m):2番目のindexの数を決定する

1からnまで未使用の数値を検索します.

再帰関数では、関数を呼び出す前に関数の呼び出しを準備することが最も重要です.

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int n,int m) {
			if(index==m) {
				//index가 m이랑 같아지면 
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
				//끝
			}
			for(int i=1;i<=n;i++) {
				if(c[i])	//이미 해당 숫자가 쓰였으면 continue;
					continue;
				//해당 숫자 사용했다고 true로 바꿔주기
				c[i] = true;
				a[index] = i;
				go(index+1,n,m);
				
				c[i]=false; //다시 사용한 것을 FALSE로 만들어 주어야함
                //함수의 호출 미리 준비.
			}
				
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,n,m);
			
		}		
	}

白俊先生の言うとおりに解いて、结局タイムアウトして、どうしてこれに会いますか?どうしてこれに会いますか?

NとM(2)

1からNまで自然数の中ですべての重複しないM個の数列の問題を求めます(昇順)
1<=M<=N<=8
NとM(1)と似ているが,昇順が異なるだけである.
自然数を選択する場合と、自然数を選択しない場合があります.

startを追加すればいいです.

indexはstartからnまで可能である.

iが

indexにある場合、index+1はi+1からnまで可能である.

c[i]->を使用する場合はtrueまたはfalse

絶対重複する数字は使用しないので関係ありません.

シーケンスxは、選択の観点から見られる.

で選択した数も記録します.

index:指数を表す

選択済

:選択済数量
->インデックスを選択するか、選択しないかを決定する必要があります.

import java.util.Scanner;

public class Main {
static boolean c[] = new boolean[10];
static int a[]=new int[10];

	static void go(int index,int start,int n,int m) {
		if(index==m) {
			for(int i=0;i<m;i++) {
				System.out.print(a[i]);
				if(i != m-1)
					System.out.print(' ');
			}
			System.out.println();
			return;
		}
		for(int i=start;i<=n;i++) {
			c[i] = true;
			a[index] = i;
			go(index+1,i+1,n,m);
			c[i]=false;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int m = sc.nextInt();
		go(0,1,n,m);
	}		
}

NとM(3)

1からNまでの自然数からM個の数列を選択する問題(繰り返し選択可能)
1<=M<=N<=7
重複選択を排除するだけです.

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int n,int m) {
			if(index==m) {
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
			}
			for(int i=1;i<=n;i++) {
				c[i] = true;
				a[index] = i;
				go(index+1,n,m);
				c[i]=false;
			}
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,n,m);
		}		
	}

あ~~これもタイムアウト、、、~~

NとM(4)

1からNまでのすべての自然数からM個の数列を選択する問題(繰り返し選択可能、非降順)
1<=M<=N<=8

NとM(2)に昇順startが加わる、NとM(3)で使用するか否か記録X

start~nがiである、i+1から~n(繰り返し可能であるため)

まで可能である.

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int start,int n,int m) {
			if(index==m) {
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
			}
			for(int i=start;i<=n;i++) {
				c[i] = true;
				a[index] = i;
				go(index+1,i,n,m);
				c[i]=false;
			}
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,1,n,m);
		}		
	}

NとM(5)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		static int num[] = new int[10];
		
		static StringBuilder go(int index,int n,int m) {
			if(index==m) {
				StringBuilder sb = new StringBuilder();
				for(int i=0;i<m;i++) {
					sb.append(num[a[i]]);
					if(i != m-1)
						sb.append(" ");
				}
				sb.append("\n");
				return sb;
			}
			StringBuilder res = new StringBuilder();
			for(int i=0;i<n;i++) {
				if(c[i])	
					continue;
				c[i] = true;
				a[index] = i;
				
				res.append(go(index+1,n,m));
				c[i]=false;
			}
			return res;
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			for (int i=0;i<n;i++) {
				num[i]=sc.nextInt();
			}
			Arrays.sort(num,0,n);
			System.out.println(go(0,n,m));
		}		
	}

Reference

この問題について([コケ]05-ブルトポス(NとM)), 我々は、より多くの情報をここで見つけました https://velog.io/@tms01365/코테05-브루트-포스N과-M

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

Java同時メモ(14)----ブロックキュー

TIL 2. position, inline, float