アルゴリズムの設計と分析——第3編、逆推力など

前に書いてあると--
今回は主にアルゴリズムを話し始めました.主に、分治法、貪欲法、動的計画が主です.これらは問題を処理する思想だと思います.何か蛮力法、逆推法なども思想ですが、もっと多いです.これもツールです.前の3つの方法の中でよく使われています.特に逆推です.実は私も逆さまに押すのはそんなに不思議ではないと思います.結局、私たちが数学の問題をするときは、普通の順序で考えられないことが多いです.逆さまに押すとうまくいくと思います.そして、これらのアルゴリズムは、訓練としか言えないと思います.実際に応用するときは、適当に止めなければなりません.あまり強要しないでください.実際の問題は一般的にこれらの訓練問題よりずっと複雑です.だから私はずっとこれがただ1つの思想を鍛えるだけだと思っています!
第二編-
私は以下の3つの问题が比较的に简単だと思って、1つ目の问题は少し难しいですが、本の上の例題なので、多くの工夫をして考えていません.逆に考えると、この问题もあまり细く考えられません.多くの数学思想の支えが必要です.特に最初から数学モデルを作る必要があるので、方法をマスターしてテクニックを悟るといいです.なぜこのように計算するのかについては、なぜこのように計算するのが最も節約的なのか、議論しないほうがいい.
1.砂漠を越えた問題
1台のジープが1000キロの砂漠を通り抜けた.ジープの総燃費は500ガロン、燃費は1ガロン/キロです.砂漠にはガソリンタンクがないので、まずこの車で砂漠に臨時ガソリンタンクを建てなければなりません.ジープ車が最小限の燃費で砂漠を通り抜ける場合は、それらの場所にガソリン貯蔵庫を建設し、あちこちに貯蔵されているガソリン量を貯蔵しなければならない.
 
アルゴリズム設計:
この問題は最小限の燃費、つまり最後に砂漠を通り抜けた後にちょうど油量が0であることを要求するため、同時に、明らかに、直接運転するのは通り抜けることができなくて、中間にガソリン貯蔵庫を架けて、この車を使うしかなくて、一度に500ガロンを持ってしかも歩いて帰っても油を消費しなければならなくて、もし問題を分析しているならばとても複雑で手がつけられません.しかし、逆さまに押すと、まだ跡があることがわかります.
終点から逆転し、ちょうど油量が0であれば、終点から500キロ離れたところにAが1つのガソリン貯蔵庫を設立し、500ガロンを貯油し、A点後のガソリン貯蔵庫をB点、B点からA点まで油を運ぶ.条件を満たす最良の案はB点からA点まで3回歩き、第1、2往復の燃費は積載量の2/3、貯油量は積載量の1/3である.3回目の一方向走行の燃費は積載量の1/3,貯油量は積載量の2/3であった.統計すると、B点の貯油量は1000ガロンで、この区間の長さは500/3キロです.
同理分析B点以降のガソリンタンクC点は、往復5回必要であるはずで、位置はB点から500/5キロ離れた位置にあり、貯油量は1500である.
 
コードは次のとおりです.

#include 
 
int main()
{
       int dis[100],k,oil[100];
       dis[1]= 500;
       k= 1;
       oil[1]= 500;
       do {
              k++;
              dis[k]= dis[k-1] + 500/(2 * k - 1);
              oil[k]= 500 * k;
       }while(dis[k] < 1000);
 
       oil[k]= 500 * (k - 1) + (1000 - dis[k]) * (2 * k - 1);
       dis[k]= 1000;
 
       int i = 0;
       for(;i

アルゴリズム解析:逆プッシュ法により,いくつかの順方向導出が扱いにくい問題を解決することができ,非常に有効である.
 
2.54枚のトランプ、2人は交代でトランプを取って、一人一人が毎回最低1枚を取って、最大4枚を取って、誰が最後の1枚を持って誰が負けます.シミュレーションコンピュータが先にカードを取り、必ず勝つアルゴリズムを作成します.
 
アルゴリズム設計:
題意によって、先に取らなければならず必ず勝つということは、54枚から初めて取った札の数を引いた後、1ラウンドごとに相手が先に取って、自分が後に取って、最後のラウンドまで、ちょうど1枚の札が残っていて、相手の札の数が1つ-4の乱数であることを理解することができます.その場合、相手の毎回の札の数は確定できませんが、1ラウンドごとに札の数は確定できます.相手が取り終わった後、自分で一定の数のカードを持って一定の達成可能な数字を作ることができて、この数字は明らかに5であるべきで、つまり1ラウンドごとに5枚のカードを持って、最後に1枚残って、しかも前にすでに持っていったカードを減らして、明らかに、先に3枚持って行った後に、まだ51枚残って、1ラウンドごとに5枚持って行って、10ラウンドの後で、まだ1枚残って、この時必ず勝つことができます.
 
コードは次のとおりです.

#include 
#include 
#include 
 
int main()
{
       int i = 3;//         
       int n = 54;//      
       int i_times = 1;//       
       int p;//       ， 1-4         
       srand(time(0));
       while(n > 0)
       {
              p= rand()%4 + 1;
              printf("the%d time computer select %d paper and you %d paper
",i_times,i,p);
              n-= i+p;
              printf("nowthe paper has left %d
",n);
              i_times++;
              i= 5 - p;//         ，                5 
              if(n - i == 1) {//      ，          ，      
                     printf("the%d time computer select %d paper and you have the last one
",i_times,i);
                     break;
              }
       }
       return 0;
}

アルゴリズムの分析:このアルゴリズムの肝心な点はどのように最后に必ず1枚のカードを他の侧に残すことを保证して、その上1ラウンドごとにカードを持って同じ数量を保证してやっと制御することができて、しかし1ラウンドごとに先にカードを取って、コントロールすることができなくて、相手が先にカードを取ってからやっと彼の数量によって更に何枚持つべきかを决めることができて、この时ルールによって、必ず先に持ってまた胜ちなければなりませんこのとき、まず何枚を取るかを考えて、それから1ラウンドごとにカードを取り始めて、最後に1枚のカードを残して、順調にコードを書く必要があります.
 
 
3.駒の山があり、2枚2枚の数があり、最後に1枚残っている.3枚3枚の数、最後に残り2枚.5枚5枚の数で、最後に4枚残ります.6枚6枚の数、最後に残り5枚.7枚7枚の数で、最後にちょうど数え終わった.この駒の山が少なくとも何枚あるかを求めるようになる.
 
アルゴリズム設計:
题目から见て、明らかに1つの数を求めて、この数は2に対して1を求めて、3に対して2を求めて、5に対して4を求めて、6に対して5を求めて、7に対して整除して、蛮力法を使って、最小の数の7から累积して、条件を満たすまで终わります
 
コードは次のとおりです.

int main()
{
 
       int i = 7;
       while(1) {
              if(5 == i % 6 && 4 == i% 5 && 2 == i % 3 &&1 == i % 2) {
                     printf("        %d
",i);
                     break;
              }else
                     i+= 7;
       }
 
       return 0;
}

アルゴリズム分析:以上は実際に列挙法を採用し、各数を演算して余数を比較し、すべての条件に合致する数が現れるまで、ここで簡単に設計した.