「オイラープロジェクト71～80」の編集履歴（バックアップ）一覧はこちら

オイラープロジェクト71～80 - (2012/08/27 (月) 19:43:50) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い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);
 }



公式を使ってみたら驚くほど速くなった。
公式すごいな。

 #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);
 }

*問い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);
 }