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

概要

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

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

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

問題１

Q37：サイコロの反転

解答１

ソースコード

#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 next_dice(int dice){
   int top=(int)(dice/pow(6,5));
   int p=pow(6,5-top);
   int left=(int)(dice/p);
   int right=dice%p;
   
   return (right+1)*pow(6,top+1)-(left+1);
}

//numが配列の何番目かを取得する。存在しない場合は-1を返す
int getIndex(std::vector<int> v,int num){
   auto itr = std::find(all(v),num);
   int index;
   if(itr!=v.end()){
       index=std::distance(v.begin(), itr);
   }else{
       index=-1;
   }
   return index;
}


int main(void){
   //探索のログ 0:未探索 1:ループではない 2:ループしている
   std::vector<int> dice(pow(6,6),0);

   rep(i,pow(6,6)){
       if(dice[i]==0){
           std::vector<int> check;
           
           //次のサイコロを探す
           while(dice[i]==0 && getIndex(check,i)==-1){
               check.push_back(i);
               i=next_dice(i);
           }
           
           int index=getIndex(check,i);
           
           //探索した記録をする
           if(index>=0){
               rep(j,check.size()){
                   if(j<index){
                       dice[check[j]]=1;
                   }else{
                       dice[check[j]]=2;
                   }
               }    
           }else{
               rep(j,check.size()){
                   dice[check[j]]=1;
               }
           }
       }
   }
   
   int cnt=0;
   //ループしていないところのみカウント
   rep(i,pow(6,6)){
       if(dice[i]==1){
           cnt++;
       }
   }
   std::cout << cnt << std::endl;
   
}

実行結果

問題２

Q38：7セグメントコードの反転

解答２

ソースコード

#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

string bit[]={"1111110","0110000","1101101","1111001","0110011","1011011","1011111","1110000","1111111","1111011"};//点灯パターン

std::vector<int> num={0,1,2,3,4,5,6,7,8,9};
int main(void){
   int min=100;
   do{//すべての並び順を検索する
       int cnt=0;
       repi(i,1,num.size()){
           //排他的論理和のために2進数に変換
           bitset<7> b1(bit[num[i-1]]);
           bitset<7> b2(bit[num[i]]);
           
           std::bitset<7> result = b1 ^ b2;    //排他的論理和をとる
           cnt+=result.count();    //1のビット数をカウント
           if(cnt>min){
               break;
           }
       }
       //最小なら更新
       if(cnt<min){
           min=cnt;
       }
   }while(std::next_permutation(all(num)));
   std::cout << min << std::endl;
}

実行結果

今回の学び

・q38について、本のq38_01.rbと違い、文字列変換はしていないため、処理時間が短い。また、処理時間を減らすための工夫として、その時点でのカウントが現在の最小値を超えた場合、breakするようにした。時間を計測したところ以下のようになった。

break処理をしない場合→612ミリ秒
break処理をした場合　→310ミリ秒

問題によって、この処理の効果がない場合も考えられるが(ほとんどのパターンで同じ数字になる場合など)、今回の場合はかなり有効に働いたと思われる。

参考文献

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

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