列挙アルゴリズムの例題

16273 ワード

列挙アルゴリズム:問題のすべての可能な解を一つ一つ列挙し、一つ一つ列挙する過程で、各可能な解が問題の真の解であるかどうかを検証する.
列挙時の注意:漏れず、重複せず、可能な解は限られている.
列挙アルゴリズムは問題を二つの部分に分解する.
1.一つ一つ列挙:
循環構造考慮する問題:どのように循環変数を設定するか、初期値、最終値、付加価値、循環変数が検査に参加するかどうか.
2.検査:
分岐構造考える問題:検証対象が誰であるか,論理判断後の2つの結果をどのように処理するか.
注意:ループ変数と判断対象が同じ変数であるかどうか.
このアルゴリズムの入出力処理:ほとんどの場合、サイクル変数を用いて代替される.
例1.1-1000の中で3で割り切れる数を求めます.
// 1-1000 ,  3    
public class Enum02 {
	public static void main(String args[]) {
		int sum = 0;
		for(int i = 1;i <= 1000; i++){
			if(i % 3 == 0) {
				System.out.println("  3     :"+i);
				sum = sum + 1;
			}
		}
		System.out.println("  3        :"+sum);
	}
}

例2.1~1000のうち7と11で割り切れるすべての数を見つけます.
//1-1000   7 11    
public class Enum03 {
	public static void main(String args[]) {
		int sum = 0;
		for(int i = 1; i <= 1000; i++) {
			if(i % 7 == 0 && i % 11 == 0) {
				System.out.println("  7 11     :"+ i);
				sum = sum + 1;
			}
		}
		System.out.println("  7 11     "+sum+" 。");
	}
} 

例3.文書に塗られた数字を推定する.
(数字を1つ塗る)
1.文書2545 xにはビット数が欠けていますが、この5ビット数が37または67の倍数であることを知っています.アルゴリズムを設計し、条件を満たすすべての5ビット数を出力し、このような数の個数を統計してください.
  • この5桁を直接列挙し、検査を行う.
  • 個の桁数の数字を列挙し、この5桁を式で表現し、最後に検証する.
  • public class Enum04 {
    	public static void main(String args[]) {
    		int sum = 0;
    		for(int n = 25450; n <= 25459; n++) {
    			if(n % 37 == 0 && n % 67 == 0) {
    				sum = sum + 1;
    				System.out.println("         :"+n);
    			}
    		}
    		System.out.println("          :"+sum);
    	}
    }
    
    //         ,              ,      。
    public class Enum0401 {
    	public static void main(String args[]) {
    		int sum = 0;
    		for(int i = 0;i <= 9; i++) {
    			int n = 25450 + i;   //   
    			if(n % 37 == 0 || n % 67 == 0) {
    				System.out.println("         :"+n);
    				sum = sum + 1;
    			}
    		}
    		System.out.println("         "+sum+" 。");
    	}
    }
    

    (隣接する2つの数字を塗ります)
    2.ある文書1 xx 47は、千桁と百桁が欠けていますが、この5桁は57または67の倍数です.条件を満たすすべての5桁を出力するアルゴリズムを設計し、このような数の個数を統計してください.
    //   1xx47,        ,   5   57 67   ,       ,         5  ,          。
    public class Enum0402 {
    	public static void main(String args[]) {
    		int sum = 0;
    		for(int i = 0; i<= 99; i++) {
    			int n = 10047 + i * 100;//5      
    			if(n % 57 == 0 || n % 67 == 0) {
    				System.out.println("         :"+n);
    				sum = sum + 1;
    			}
    		}
    		System.out.println("         "+sum+" 。");
    	}
    }
    

    (隣接しない2つの数字を塗ります)
    3.ある文書1 x 4 x 7は、千桁と十桁が欠けているが、この5桁は57または67の倍数である.アルゴリズムを設計し、条件を満たすすべての5桁を出力し、このような数の個数を統計してください.
    public class Enum0403 {
    	public static void main(String args[]) {
    		int sum = 0;
    		for(int n = 0;n <= 9; n++){
    			for(int m = 0;m <= 9; m++) {
    				int k = 10407 + n * 1000 + m * 10;//   
    				if(k % 57 == 0 || k % 67 == 0) {
    					System.out.println("         :"+k);
    					sum = sum + 1;
    				}
    			}
    		}
    		System.out.println("         "+sum+" 。");
    	}
    }

    例4.1000以内の素数を出力します.
    素数とも呼ばれる.1より大きい自然数のうち、1とこの整数自体を除いて、他の自然数では割り切れない数を指す.1と0は素数でも合数でもない.
    毎回1つの数を取り出し、その数を2からそれ自体に順番に割るだけで、余数を見て、余数が0の場合、きっと素数ではなく、全部除いても余数が0の場合がなければ、素数に違いない.
    偶数は素数ではないに違いないので、増加するときは奇数の形で増加し、奇数の中で非素数の数を取り除くことができます.
    public class Enum05 {
    	public static void main(String args[]) {
    		int sum = 0;
    		int i = 0;
    		int j = 0;
    		for(i = 3;i <= 1000; i = i+2) {
    			for( j = 2; j < i; j++) {
    				if(i % j == 0) {
    					break;
    				}
    			}
    			if(i == j) {
    				System.out.println("  --------"+i);
    				sum = sum + 1;
    			}
    		}
    		System.out.println("1-1000     "+sum+" 。");
    	}
    }
    

    例5.水仙の数を探す
    すべての「水仙の花の数」を出力します.「水仙の花の数」とは、その各数字の3桁の立方メートルと、その数そのものに等しいことを意味します.例えば、153は「水仙の花の数」です.153=13+53+33です.
    public class Enum06 {
    	public static void main(String args[]) {
    		int g = 0;  //    
    		int s = 0;  //    
    		int b = 0;  //    
    		int sum = 0;
    		for(int i = 100;i <= 999; i++) {
    			b = i / 100;
    			g = i % 10;
    			s = (i - b*100)/10;
    			if(i == (b*b*b + s*s*s + g*g*g)) {
    				System.out.println("    ---------"+i);
    				sum = sum + 1;
    			}
    		}
    		System.out.println("     "+sum+" 。");
    	}
    }
    

    例6.ニワトリとウサギの同籠問題
    今は鶏とウサギが同じかごを持っていて,上には35頭,下には九十四足がある.ニワトリとウサギはそれぞれ何匹ですか.
    public class Enum07 {
    	public static void main(String args[]) {
                    //   
    		for(int j = 0;j <= 35;j++){
    			if(94 == 2*j + 4*(35-j)) {
    				int t = 35 - j;
    				System.out.println("  -----"+j+" ----  ----"+t+" 。");
    			}
    		}
    		//   
    		for(int j = 0;j <= 35; j++) {
    			for(int t = 0; t <=35; t++) {
    				if((j + t == 35) && (2*j + 4*t == 94)) {
    					System.out.println("  -----"+j+" ----  ----"+t+" 。");
    				}
    			}
    		}
    	}
    }
    

    例7.百鶏百元問題.
    ニワトリの翁の1、値打ちの5、ニワトリの母の1、値打ちの3、ニワトリの雛の3、値打ちの1、百元は百鶏を買って、翁に聞いて、母、雛の各幾何学?
    雄鶏は1羽5元で、雌鶏は1羽3元で、3羽のニワトリは1元で、100元で100羽のニワトリを買って、雄鶏、雌鶏、ニワトリはそれぞれ何羽ですか?
    public class Enum08 {
    	public static void main(String args[]) {
    		for(int g = 0;g <= 20; g++) {
    			for(int m = 0;m <= 33; m++) {
    				int x = 100 - g - m;
    				if((5*g + 3*m +x/3 == 100)) {
    					System.out.println("   ----"+g+" ,   ------"+m+" ,   -----"+x+" 。");
    				}
    			}
    		}
    	}
    } 

    例8.列挙法による「演算子の記入の問題」の解決
    1,問題の説明:以下の式の中で、“+”、“-”、“*”、“/”の4つの演算子を追加して、この式を成立させます.5 5 5 5 5=5 
    2,アルゴリズム解析:上記式の左側には5つの数字があり,合計4つの演算子が必要である.タイトルの要求に応じて、2つの数字の間の演算子は4つしか選択できません.具体的なプログラミングでは,ループによって各種演算子を埋め込み,演算式の左側の値が右側の値に等しいか否かを判断することができる.また、除算記号が入力されている場合、右側の数は0ではなく、乗算除算の優先度が増減の優先度より高いことを保証します.
    転載先:https://juejin.im/post/5c526d2d518825551e288c61