「プログラマ脳を鍛える数学パズル」を解いてみる中級編#11【アルゴリズム学習】

概要

翔泳社から出版されている「プログラマ脳を鍛える数学パズル」のプログラミング問題をC++で解きます。
この本ではRuby,JavaScript,Cでの解答はありますが、C++は載っていないため練習として解いてみようと思います。
記事、コード共にまだまだな部分も多いので、何かお気づきの点があれば、コメントお願いいたします。

入門編はコチラ
初級編はコチラ
中級編はコチラ

ぜひ、いいねと思ったらスキお願いいたします！！！
見出し画像は最近食べたおいしいものです。

問題１

Q51：パーフェクトシャッフル

解答１

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long

//引数のvectorを問題のルールでシャッフルする関数
std::vector<int> shuffel(std::vector<int> v){
   std::vector<int> result(v.size(),0);
   rep(i,v.size()){
       if(i%2==0){
           result[i]=v[i/2];
       }else{
           result[i]=v[i/2+v.size()/2];
       }
   }
   return result;
}

int main(void){
   int ans_f=0;//2(n-1)回目で初めて元に戻ったもの
   int ans_s=0;//何回も元に戻っているが、2(n-1)回目の時も戻っているもの
   repi(n,1,101){
       std::vector<int> tranp;
       
       //初期化
       repi(i,1,2*n+1){
           tranp.push_back(i);
       }

       bool flag=true;
       std::vector<int> first=tranp;
       
       //シャッフルを繰り返す
       rep(i,2*(n-1)){
           tranp=shuffel(tranp);
           if(i!=2*(n-1)-1 && tranp==first){//2*(n-1)回目の時はカウントしない
               flag=false;//2(n-1)以前に元に戻っている場合flagを変更
           }
       }
       
       //問題の条件に合うようにカウントする
       if(tranp==first){
           ans_s++;
           if(flag && n!=1){   //n=1の時はシャッフルが行われていないので除外
               ans_f++;
           }
       }
   }
   std::cout << "2(n-1)回目で初めて元に戻った" << std::endl;
   std::cout << ans_f << std::endl;
   std::cout << "何度も元に戻るが、2(n-1)回の時も元に戻っている" << std::endl;
   std::cout << ans_s << std::endl;
   
}

実行結果

問題２

Q52：同時に終わる砂時計

解答２

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define repi(i,a,n) for(int i = (int)a; i < (int)(n); i++)
#define ll long long

int N=8;

//過去に探索したことがあるかチェックする
bool check(std::vector<std::vector<int>> timer_log,std::vector<int> pos_log,std::vector<int> v,int pos){
   rep(i,timer_log.size()){
       if(timer_log[i]==v && pos_log[i]==pos){
           return true;
       }
   }
   return false;
}

int main(void){
   std::vector<int> goal(N,1);
   int cnt=0;
   
   //砂時計の初期化
   std::vector<int> sand_timer;
   repi(i,1,N+1){
       sand_timer.push_back(i);
   }
   
   //全ての並び替えに対して探索
   do{
       int pos=0;
       std::vector<int> timer=sand_timer;
       std::vector<std::vector<int>> timer_log;
       std::vector<int> pos_log;

       //ループにならない限り繰り返す
       while(!check(timer_log,pos_log,timer,pos)){
           if(goal==timer){
               cnt++;
               break;
           }
           
           timer_log.push_back(timer);
           pos_log.push_back(pos);
           
           //時間を経過させる
           rep(i,timer.size()){
               timer[i]=max(0,timer[i]-1);
           }
           //砂時計を反転させる
           rep(j,sand_timer[pos]){
               int k=(pos+j)%N;
               timer[k]=sand_timer[k]-timer[k];
           }
           pos=(pos+1)%N;
       }
       
   }while(next_permutation(all(sand_timer)));
   
   std::cout << cnt << std::endl;
}

実行結果

今回の学び

・q51のシャッフルの手順について、本よりシンプルに実装できた。本ではおそらく分かりやすさ重視のために、2分割して新しい変数に代入している。今回実装した方法としては、シャッフル後の並び替えの順番はi番目の数字は元のカードの順番のi/2番目と（i+size()/2）番目なので、その数字を新しい変数に代入した。

・q52について、過去に探索したかどうかを調べるための砂時計のログとして、砂時計全体の残り時間だけでなく、今どこをひっくり返しているかも併せて記録する必要があった。このことに後で気づいたため、ソースコードでは別々の変数で保存しているが、pairや構造体などを使って実装したほうが、シンプルに実装できたと思う。

参考文献

「プログラマを鍛える数学パズル」著:増井敏克

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問