「プロジェクトオイラー問い61～70」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問い61～70 - (2012/12/28 (金) 18:28:25) の編集履歴(バックアップ)

---

問い61

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2061
三角数, 四角数, 五角数, 六角数, 七角数, 八角数に関する問題。

解法
問題をグラフに翻訳して深さ優先探索で解決です。
少し手の込んだ処理を書いてますがもしかしたらもっとシンプルになるかもしれません。

#include<stdio.h>
#include<vector>
#include<map>

std::map<int,std::vector<int> > memo[9];
bool spents[9]={false,false,false,true,false,false,false,false,false};
 
void saiki(int start,int num,int deep,int sum){
	if(deep==6){
		if(start==num){
			printf("ans=%d\n",sum);
		}
	}else{
		for(int i=3;i<=8;i++){
			if(spents[i]==false&&memo[i].find(num)!=memo[i].end()){
				spents[i]=true;
				for(int j=0;j<memo[i][num].size();j++){
					saiki(start,memo[i][num][j],deep+1,sum+num*100+memo[i][num][j]);
 				}
				spents[i]=false;
			}
		}
	}
}

int main(){
for(int i=1;(i*(i+1))/2<10000;i++){
 		int n=(i*(i+1))/2;
		if(1000<=n&&n<=9999)memo[3][n/100].push_back(n%100);
		n=i*i;
		if(1000<=n&&n<=9999)memo[4][n/100].push_back(n%100);
		n=(i*(i*3-1))/2;
		if(1000<=n&&n<=9999)memo[5][n/100].push_back(n%100);
		n=i*(2*i-1);
		if(1000<=n&&n<=9999)memo[6][n/100].push_back(n%100);
		n=(i*(5*i-3))/2;
		if(1000<=n&&n<=9999)memo[7][n/100].push_back(n%100);
		n=i*(3*i-2);
		if(1000<=n&&n<=9999)memo[8][n/100].push_back(n%100);
	}
	for(std::map<int,std::vector<int> >::iterator it=memo[3].begin();it!=memo[3].end();it++){
		for(int i=0;i<(*it).second.size();i++){
			saiki((*it).first,(*it).second[i],1,(*it).first*100+(*it).second[i]);
		}
	}
}

問い62

立法数の各桁をまた並び変えると立法数になるものがある。
丁度五つの並び変えを持つ最小の立法数を求めよ。

解法
立法数を各桁に分解し出てきた数字の出現個数数えて分類します。
アナグラムになってるものを全部同じと分類します。
後は答えが見つかるまで上限を増やしていけば大体答えは出ます。

#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>

struct CUBE{
	int keta[10];
	__int64 num;
	void set(__int64 n)
	{
		num=n*n*n;
		n=num;
		memset(keta,0,sizeof(keta));
		while(n!=0)
		{
			keta[(int)(n%10)]++;
			n/=10;
		}
	}
	bool operator<(const CUBE& c)const
	{
		for(int i=0;i<10;i++)
		{
			if(keta[i]!=c.keta[i])return keta[i]<c.keta[i];
		}
		return false;
	}
};
int main(){
	__int64 num=1,limit=1;
	std::map<CUBE,int> memo;
	CUBE c;
	for(int i=0;i<15;i++)limit*=10;//とりあえず１５桁目あたりまで探索してみる見つからなければ桁を増やす
	while(num*num*num<limit){
		c.set(num);
		if(memo.find(c)==memo.end())memo[c]=0;
		memo[c]++;
		num++;
	}
	__int64 ans=limit;
	for(std::map<CUBE,int>::iterator it=memo.begin();it!=memo.end();it++){
		if((*it).second==5){
			if(ans>(*it).first.num)ans=(*it).first.num;
		}
　	}
　	std::cout<<"\nans="<<ans;
}

問い63

5桁の数 16807 = 75は自然数を5乗した数である. 同様に9桁の数 134217728 = 89も自然数を9乗した数である.
自然数を n 乗して得られる n 桁の正整数は何個あるか?

解法

10^nを考えｆ(a)を桁数を返す関数とするとf(10^n)>nが成り立ち１０以上の数ではすべてこれが成り立ちます。
よって９以下の数だけ検討すれば良いと分かります。
対数をとって地道に掛け算するだけです。
９以下ではｎが増加するとある時点でf(a^n)<nとなるので計算の打ち切りをここに設定します。
__int64だと９の答えがあふれるようです。

#include<stdio.h>
#include<math.h>
#include<set>
#include<iostream>
int main(){
	int ans=0,r,count=0;
for(__int64 i=1;i<10;i++){
		double t=log(i)/log(10);
		r=1;
		while(1){
			int t1=(int)(t*r+1);
			count++;
			if(t1<r)break;
			if(t1==r)ans++;
			r++;
		}
	}
	
	printf("ans=%d 計算量%d\n",ans,count);
}