*問い74 http://projecteuler.net/problem=74 各桁の階乗をとりそれを合計する操作を繰り返すと数字が循環する。 １００万以下の６０個目まで循環しない数字は何個あるか？ メモ化で少しだけ高速化。 後は愚直に計算するだけです。 #include<stdio.h> #include<set> #include<iostream> __int64 perm[10]; std::set<__int64> memo; const int up=1000000; int lens[up]={0}; int saiki(__int64 num){ int re; if(memo.find(num)!=memo.end()){ re=0; }else if(num<up&&lens[(int)num]!=0){ return lens[(int)num]; }else{ memo.insert(num); __int64 next=0,m=num; while(num!=0){ next+=perm[(int)num%10]; num/=10; } //std::cout<<next<<" "; re=saiki(next)+1; if(m<up)lens[(int)m]=re; } return re; } int main(){ perm[0]=1; for(int i=1;i<10;i++){ perm[i]=perm[i-1]*i; } int ans=0; for(int i=1;i<up;i++){ memo.clear(); ans+=(saiki(i)==60); } printf("%d\n",ans); } *問い76 100の分割数を求める問題。 メモ化を使ってみたが無意味な処理だったかもしれない。 最悪のコード実行速度となっている。 今からきちんと公式の意味と式を勉強してコードを書きなおそうと思う。 #include<stdio.h> #include<string.h> int ans=0; int memo[101][101]; int saiki(int n,int m){ if(memo[n][m]!=0){ ans+=memo[n][m]; return memo[n][m]; }else if(n==0){ ans++; return 1; }else{ int sum=0; for(int i=m;i<=n;i++){ memo[n-i][i]=saiki(n-i,i); sum+=memo[n][i]; } return sum; } } int main(){ memset(memo,0,sizeof(memo)); ans=0; saiki(100,1); printf("%d",ans-1); } 公式を使ってみたら驚くほど速くなった。 公式すごいな。 #include<stdio.h> #include<string.h> int memo[101][101]; int P(int k,int n){ if(k>n)return 0; if(k==n)return 1; if(memo[k][n]!=-1)return memo[k][n]; memo[k][n]=P(k+1,n)+P(k,n-k); return memo[k][n]; } int main(){ memset(memo,-1,sizeof(memo)); printf("%d\n",P(1,100)-1); } *問い78 自然数nの分割数を求める関数P(n)を考えた時p(n)が１００万で割れる最小のｎを求めよという問題。 問い76の公式を使っても遅いのでＷｉｋiの分割数の解説にあったもう一段早い処理を実装。 問い７６で解いた公式はまあなんとなくメモ化がいい具合に聞く原理は分かるのだが、こちらになると一体どういう原理なのか想像もつかない。 多分この辺でも初等整数論なんだろうけど俺には整数論は難しいすぎるな。 #include<stdio.h> #include<vector> #include<iostream> const __int64 mask=1000000; int main(){ std::vector<__int64> memo; int s[]={1,1,2,3,5,7,11,15}; for(int i=0;i<8;i++)memo.push_back(s[i]); int k=8; __int64 sum; int sa,down,t,p,base; while(1){ sum=0; sa=1; t=1; down=1; base=1; std::cout<<k<<"\n"; while(1){ if(k<base)break; sum+=(t*memo[k-base])%mask; if(k<base+sa)break; sum+=(t*memo[k-base-sa])%mask; down+=3; base+=down; sa++; t*=-1; //std::cout<<"("<<base<<" "<<sa<<")"; } //std::cout<<sum<<"\n"; sum=sum%mask; if(sum==0)break; memo.push_back(sum); k++; } std::cout<<k; } *問い80 1～100までの平方根のうち無理数になる数の集合を考える。 １００桁目までの各桁の和の合計はどうなるか？ このサイトを参考に問題を解く。 http://www004.upp.so-net.ne.jp/s_honma/root.htm サイト通りだと桁数が64bit整数で溢れそうだったので苦手なＬｉｓｐで挑戦。 Ｌｉｓｐに不慣れなために構文エラーなどで恐ろしく時間がかかった。 オイラープロジェクトは学びのためのサイトだろうから調べ物しながら解くことで数学とアルゴリズムに関する知識を学ぶのが本筋だろうから調べながら勉強するのが正しい気がする。 Ｌｉｓｐで集計する方法がよくわからなかったのででてきた数字列をＥｘｃelで集計して、最後に余分な無理数でない数を引いてアセプト。 (defun mysqrt (n m sum deep) (cond ((= deep 0) (let ((r (floor (sqrt n)))) (mysqrt (* (- n (* r r)) 100) (* (+ r r) 10) r (+ deep 1)))) ((= deep 100) sum ) (t (dolist (x '(9 8 7 6 5 4 3 2 1 0)) (let ((r (* (+ m x) x))) (if (<= r n) (return (mysqrt (* (- n r) 100) (* (+ m x x) 10) (+ sum x) (+ deep 1))))))))) mysqrt (dotimes (x 100) (print (mysqrt (+ x 1) 0 0 0)))
