アルゴリズム洗脳シリーズ(8編)——第一篇のデリバリー思想

5816 ワード
データ構造 プログラミング アルゴリズム exception 生活 Random
私のように最前線で奮闘している私たちは、プログラミングの勉強について言えば、XX言語を習得すればOKということです.実は私たちが理解しているのは、わずかな偏差があります.
三分の一、ほんとうのプログラミングはプログラミング=データ構造+アルゴリズム+XX言語です.
    はい、XX言語はただの道具です.私たちはペンで字を書くことを知っていますが、張恨み水を傾倒させるいい字を書くことができるとは限りません.実は私も言ったことがあります.
アルゴリズムはプログラムデザインだけではなく、私たちの生活の中にも至るところにアルゴリズムが存在しています.例えば、私が大学二年生の時にCを勉強したことを覚えています.
	@Test
	public void testMeiMei() {
		Random random = new Random();

		Scanner scanner = new Scanner(System.in);
		int mm = random.nextInt(17) + 16;

		int guess = 0;

		int count = 0;

		System.out.println(mm + "     ，      (16,32)
");

		do {
			System.out.println("           ：\t");

			try {
				guess = scanner.nextInt();
			} catch (Exception e) {
				return;
			}
			if (guess < mm)
				System.out.println("  !
");

			if (guess > mm)
				System.out.println("  ！
");

			if (guess == mm)
				System.out.println("  ，   ！
");

			count = count + 1;

		} while (mm != guess);

		System.out.println("     ：\t" + count + " ");

	}
この問題に対して、みんなはどのように“速くて安定します”のはmmの年齢を推測しますか?アルゴリズムが分からない人はforループで検索しますが、この複雑さはO(n)です.
アルゴリズムを知っている人は年齢規則という特徴を利用して「二分検索」を行います.この複雑さはlog 2 Nです.だから、アルゴリズムを理解することは、実際の応用においてより良い解決策をもたらすことができます.
 
はい、もういいです.今日は主に「デリバリー思想」を話します.
コンセプト
     すでに知られている条件を利用して、特定の関係を利用して徐々に推して、最終的に結果を得るまでは、コアは常に既存の情報を利用して新しいものを導き出すことです.
 
二:分類
     もちろん、「順押し」と「逆押し」の2種類があります.
     条件から結果を出す.
     逆推:結果から条件を出す.
ほほほ、感じのが1種のpolicemanが事件を解決する感じがあるのではありませんか?
 
例を挙げます
＜1＞順推しの例
      大学に行ったことがある人なら、有名な「フィボナッチ」の数を知っていますよね.ウサギの繁殖問題を言います.
もし1対のウサギが毎月1対のウサギを生むことができるならば、それが生まれた後の第3ヶ月ごとに1対の小さいウサギを生むことができて、1対の初誕生の小さいウサギから始まるならば、1年後にできます.
ウサギはどれぐらい繁殖しますか?
考え方:実はこの問題はウサギを「1月のウサギ」「2月のウサギ」「3月のウサギ」に分けることができます.
        ①初期時:           ペア1月のウサギのサイズは、合計1対です.
        ②最初の月:        1月のウサギは2月のウサギになります.総数はまだ1対です.
        ③二ヶ月目:        2月の大きなウサギは3月のウサギになり、つがいのうさぎを繁殖させました.総数は2対です.
        ④第三ヶ月:        3月の大きなウサギtmdのペアが生まれました.先月の1月に大きなウサギが2月のウサギになりました.総数は3対です.
         ......                    ......
        F 0=1
        F 1=1
        F 2=F 0+F 1
        F 3=F 1+F 2
        ......
        Fn=Fn-2+Fn-1
 
みんなは見てみて、体現していますか?「推す」の核心の思想を手渡して、コードもとても簡単です.
	@Test
	public void feibonaqie() {
		int month = 12;
		int[] f = new int[month];
		f[0] = 1;
		f[1] = 1;

		for (int i = 2; i < month; i++) {
			f[i] = f[i - 2] + f[i - 1];
		}

		for (int i = 0; i < month; i++) {
			System.out.println("  " + i + "   ，    ：" + f[i]);
		}
	}
 
テスト結果:
  0   ，    ：1
  1   ，    ：1
  2   ，    ：2
  3   ，    ：3
  4   ，    ：5
  5   ，    ：8
  6   ，    ：13
  7   ，    ：21
  8   ，    ：34
  9   ，    ：55
  10   ，    ：89
  11   ，    ：144
 
＜2＞逆押しの例
       このお金の問題について、息子の四年間の大学生活にお金を預けています.富三代は毎月三キロしか取れません.来月の生活費として、ゼロ貯金の方式を採用しています.
   年利率は1.71%ですが、富二世代は一回でいくら預け入れますか?
 
考え方:このテーマは結果が分かりました.逆推進条件が必要です. 第48月富三代は利子を持って三kを取りに行きます.
        第47月預金は:(48ヶ月目の預金+3000)/(1+0.0171/12(月));
        第46月預金は:(47ヶ月目の預金+3000)/(1+0.0171/12(月));
         .....                    .....
        1ヶ月目の預金は次の通りです. (2ヶ月目の預金＋3000)/(1+0.0171/12(月))
    
	@Test
	public void deposit() {
		int month = 49;
		double[] f = new double[month];
		f[48] = 3000d;
		double monthRate = 1.71 / 100 / 12;

		for (int i = 47; i > 0; i--) {
			f[i] = (f[i + 1] + 3000) / (1 + monthRate);
		}
		for (int i = 48; i > 0; i--) {
			System.out.println("  " + i + "   ，    ：" + f[i]);
		}
	}
     
  48   ，    ：3000.0
  47   ，    ：5991.462166412862
  46   ，    ：8978.667565132548
  45   ，    ：11961.622253421421
  44   ，    ：14940.332279922532
  43   ，    ：17914.803684671875
  42   ，    ：20885.04249911064
  41   ，    ：23851.054746097452
  40   ，    ：26812.846439920566
  39   ，    ：29770.423586310073
  38   ，    ：32723.792182450085
  37   ，    ：35672.95821699087
  36   ，    ：38617.92767006103
  35   ，    ：41558.706513279605
  34   ，    ：44495.300709768184
  33   ，    ：47427.716214163
  32   ，    ：50355.958972627006
  31   ，    ：53280.03492286193
  30   ，    ：56199.94999412031
  29   ，    ：59115.71010721753
  28   ，    ：62027.3211745438
  27   ，    ：64934.789100076196
  26   ，    ：67838.11977939056
  25   ，    ：70737.31909967352
  24   ，    ：73632.3929397344
  23   ，    ：76523.34717001712
  22   ，    ：79410.18765261215
  21   ，    ：82292.92024126834
  20   ，    ：85171.55078140483
  19   ，    ：88046.0851101229
  18   ，    ：90916.5290562178
  17   ，    ：93782.88844019052
  16   ，    ：96645.1690742597
  15   ，    ：99503.37676237331
  14   ，    ：102357.5173002205
  13   ，    ：105207.59647524328
  12   ，    ：108053.6200666483
  11   ，    ：110895.59384541858
  10   ，    ：113733.52357432517
  9   ，    ：116567.41500793885
  8   ，    ：119397.27389264184
  7   ，    ：122223.10596663937
  6   ，    ：125044.91695997141
  5   ，    ：127862.71259452422
  4   ，    ：130676.49858404195
  3   ，    ：133486.2806341383
  2   ，    ：136292.064442308
  1   ，    ：139093.85569793844
機械学習は実戦で工夫を凝らして練習します.task 1.k-近隣アルゴリズム
简析大O表示法