「プロジェクトオイラー問い61～70」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問い61～70」(2013/01/09 (水) 14:54:23) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い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);
}
*問い65
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2065
解法
定義通り再帰的に計算してみました。
今の項から次の項を計算するもっと賢い方法とかあるかもしれません。
(defun ketaSum(n)
(apply #'+ (map 'list #'digit-char-p (princ-to-string n))))
ketaSum
(defun saiki(deep add last)
(if (= (mod deep 3) 1)
(setq add (+ 2 add)))
(let ((b (if (= (mod deep 3) 1) add 1)))
(if (= deep last)
(/ 1 b)
(/ 1 (+ b (saiki (+ deep 1) add last))))
))
saiki
(ketaSum (numerator (+ 2 (saiki 0 0 98))))
*問い67
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2067
三角形に並んだ数字表を上から下へ移動するとき経路上の数字の合計が最大になるルートを通った場合の値を答えよ。
解法
一段ずつ動的計画法を適用するだけです。
#include<stdio.h>
int main(){
int row[102]={0},a,ans=0;
for(int i=1;i<=100;i++){
int next[102]={0};
for(int j=1;j<=i;j++){
scanf("%d",&a);
next[j]=a+(row[j-1]>row[j]?row[j-1]:row[j]);
if(ans<next[j])ans=next[j];
}
for(int j=1;j<=i;j++){
row[j]=next[j];
}
}
printf("%d",ans);
}
*問い68
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2068
"magic" 5-gon ringという魔法陣のようなものを解く問題。
解法
マトリックス化して全部の数字を試すだけす。
枝刈をしたほうがよいのですが、組み合わせ数が少ないのでこれでも十分速度が出ます。
コードが品雑になるよりは楽な方を選びました。
#include<stdio.h>
#include<iostream>
int adds[5][3]={{0,1,2},
{3,2,4},
{5,4,6},
{7,6,8},
{9,8,1}};
bool spents[11];
int boards[11];
__int64 ans=0;
void saiki(int deep){
if(deep==10){
int sum=boards[0]+boards[1]+boards[2];
for(int i=1;i<5;i++){
int t=boards[adds[i][0]]+boards[adds[i][1]]+boards[adds[i][2]];
if(t!=sum)return;
}
__int64 temp=0,t;
int sp,n=10;
for(int i=0;i<5;i++){
if(boards[adds[i][0]]<n){
n=boards[adds[i][0]];
sp=i;
}
}
for(int i=0;i<5;i++){
for(int j=0;j<3;j++){
t=boards[adds[(sp+i)%5][j]];
temp*=t==10?100:10;
temp+=t;
}
}
if(ans==0||ans<temp)ans=temp;
}else{
for(int i=1;i<=10;i++){
if(i==10&&(deep==1||deep==2||deep==4||deep==6||deep==8))continue;
if(spents[i]==false){
spents[i]=true;
boards[deep]=i;
saiki(deep+1);
spents[i]=false;
}
}
}
}
int main(){
for(int i=1;i<=10;i++)spents[i]=false;
saiki(0);
std::cout<<ans;
}
*問い69
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2069
オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.
n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる.
n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ.
解法
全部検討します。
これで十分間に合います。
#include<stdio.h>
#include<string.h>
#include<time.h>
int phi(int n){
double re=n;
for(int i=2;i*i<=n;i+=(i&1)+1){
int p=i;
int count=0;
while(n%p==0){
n/=p;
count++;
}
if(count>0)re*=(1-1.0/p);
}
if(n!=1)re*=(1-1.0/n);
return (int)(re+0.5);
}
int main(){
double start=clock();
int limit=1,ansN;
for(int i=0;i<6;i++)limit*=10;
double a,ans=0;
for(int i=2;i<limit;i++){
a=phi(i);
if(ans<i/a){
ans=i/a;
ansN=i;
}
}
printf("%lf ans=%d time=%lf",ans,ansN,clock()-start);
}
*問い70
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2070
オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, n 未満の正の整数で n と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる.
1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.
面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.
1 < n < 10＾7 で φ(n) が n を置換したものになっているもののうち, n/φ(n) が最小となる n を求めよ.
解法
全部試しても大きめに見積もって000万回*3400回程度の計算量で済むので全部チェックで解けます。
#include<stdio.h>
#include<string.h>
#include<time.h>
struct S{
int count[10];
void set(int n){
memset(count,0,sizeof(count));
while(n!=0){
count[n%10]++;
n/=10;
}
}
bool operator==(const S& s){
for(int i=0;i<10;i++)if(count[i]!=s.count[i])return false;
return true;
}
};
int CustomPhi(int n){
double re=n;
for(int i=2;i*i<=n;i+=(i&1)+1){
int p=i;
int count=0;
while(n%p==0){
n/=p;
count++;
}
if(count>0)re*=(1-1.0/p);
if(count>1)return 1;
}
if(n!=1)re*=(1-1.0/n);
return (int)(re+0.5);
}
int main(){
double start=clock();
int limit=1,ansN;
for(int i=0;i<7;i++)limit*=10;
S s1,s2;
double a,ans=0;
for(int i=3;i<limit;i+=2){
a=CustomPhi(i);
if(a==1)continue;
s1.set(i);
s2.set(a);
if(s1==s2){
if(ans==0||ans>i/a){
ans=i/a;
ansN=i;
}
}
}
printf("%lf ans=%d time=%lf",ans,ansN,clock()-start);
}
*問い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);
}
*Problem 64 「N ≤ 10000 について奇数の周期をもつ連分数はいくつあるか?」 †
平方根は連分数の形で表したときに周期的であるが奇数長さの周期性を持つ連分数はn<=10000までに何個あるか？
解法
今回の問題を解いたことで連分数の原理について丸暗記でなく原理から理解できた問題。
連分数の段数を増やしていく時時無理数と有理数は混ざらないというところに秘訣があるのだと納得出来た。
連分数という概念に最初に気付いた人は少し凄いなと思う。
最初は２段とか３段だったのかも。
#include<stdio.h>
#include<math.h>
int fm,fa;
int saiki(int n,int m,int a,int deep){
if(deep==0)fm=m,fa=a;
else if(fm==m&&fa==a)return deep;
int u=n-m*m;
u/=a;
int ans=(sqrt(n)+m)/u;
return saiki(n,ans*u-m,u,deep+1);
}
int main(){
int k,ans=0;
for(int i=1;i<=10000;i++){
k=sqrt(i);
if(k*k!=i){
ans+=(saiki(i,(int)sqrt(i),1,0)&1);
}
}
printf("%d",ans);
}
*問い65
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2065
解法
定義通り再帰的に計算してみました。
今の項から次の項を計算するもっと賢い方法とかあるかもしれません。
(defun ketaSum(n)
(apply #'+ (map 'list #'digit-char-p (princ-to-string n))))
ketaSum
(defun saiki(deep add last)
(if (= (mod deep 3) 1)
(setq add (+ 2 add)))
(let ((b (if (= (mod deep 3) 1) add 1)))
(if (= deep last)
(/ 1 b)
(/ 1 (+ b (saiki (+ deep 1) add last))))
))
saiki
(ketaSum (numerator (+ 2 (saiki 0 0 98))))
*問い67
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2067
三角形に並んだ数字表を上から下へ移動するとき経路上の数字の合計が最大になるルートを通った場合の値を答えよ。
解法
一段ずつ動的計画法を適用するだけです。
#include<stdio.h>
int main(){
int row[102]={0},a,ans=0;
for(int i=1;i<=100;i++){
int next[102]={0};
for(int j=1;j<=i;j++){
scanf("%d",&a);
next[j]=a+(row[j-1]>row[j]?row[j-1]:row[j]);
if(ans<next[j])ans=next[j];
}
for(int j=1;j<=i;j++){
row[j]=next[j];
}
}
printf("%d",ans);
}
*問い68
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2068
"magic" 5-gon ringという魔法陣のようなものを解く問題。
解法
マトリックス化して全部の数字を試すだけす。
枝刈をしたほうがよいのですが、組み合わせ数が少ないのでこれでも十分速度が出ます。
コードが品雑になるよりは楽な方を選びました。
#include<stdio.h>
#include<iostream>
int adds[5][3]={{0,1,2},
{3,2,4},
{5,4,6},
{7,6,8},
{9,8,1}};
bool spents[11];
int boards[11];
__int64 ans=0;
void saiki(int deep){
if(deep==10){
int sum=boards[0]+boards[1]+boards[2];
for(int i=1;i<5;i++){
int t=boards[adds[i][0]]+boards[adds[i][1]]+boards[adds[i][2]];
if(t!=sum)return;
}
__int64 temp=0,t;
int sp,n=10;
for(int i=0;i<5;i++){
if(boards[adds[i][0]]<n){
n=boards[adds[i][0]];
sp=i;
}
}
for(int i=0;i<5;i++){
for(int j=0;j<3;j++){
t=boards[adds[(sp+i)%5][j]];
temp*=t==10?100:10;
temp+=t;
}
}
if(ans==0||ans<temp)ans=temp;
}else{
for(int i=1;i<=10;i++){
if(i==10&&(deep==1||deep==2||deep==4||deep==6||deep==8))continue;
if(spents[i]==false){
spents[i]=true;
boards[deep]=i;
saiki(deep+1);
spents[i]=false;
}
}
}
}
int main(){
for(int i=1;i<=10;i++)spents[i]=false;
saiki(0);
std::cout<<ans;
}
*問い69
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2069
オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.
n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる.
n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ.
解法
全部検討します。
これで十分間に合います。
#include<stdio.h>
#include<string.h>
#include<time.h>
int phi(int n){
double re=n;
for(int i=2;i*i<=n;i+=(i&1)+1){
int p=i;
int count=0;
while(n%p==0){
n/=p;
count++;
}
if(count>0)re*=(1-1.0/p);
}
if(n!=1)re*=(1-1.0/n);
return (int)(re+0.5);
}
int main(){
double start=clock();
int limit=1,ansN;
for(int i=0;i<6;i++)limit*=10;
double a,ans=0;
for(int i=2;i<limit;i++){
a=phi(i);
if(ans<i/a){
ans=i/a;
ansN=i;
}
}
printf("%lf ans=%d time=%lf",ans,ansN,clock()-start);
}
*問い70
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2070
オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, n 未満の正の整数で n と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる.
1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.
面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.
1 < n < 10＾7 で φ(n) が n を置換したものになっているもののうち, n/φ(n) が最小となる n を求めよ.
解法
全部試しても大きめに見積もって000万回*3400回程度の計算量で済むので全部チェックで解けます。
#include<stdio.h>
#include<string.h>
#include<time.h>
struct S{
int count[10];
void set(int n){
memset(count,0,sizeof(count));
while(n!=0){
count[n%10]++;
n/=10;
}
}
bool operator==(const S& s){
for(int i=0;i<10;i++)if(count[i]!=s.count[i])return false;
return true;
}
};
int CustomPhi(int n){
double re=n;
for(int i=2;i*i<=n;i+=(i&1)+1){
int p=i;
int count=0;
while(n%p==0){
n/=p;
count++;
}
if(count>0)re*=(1-1.0/p);
if(count>1)return 1;
}
if(n!=1)re*=(1-1.0/n);
return (int)(re+0.5);
}
int main(){
double start=clock();
int limit=1,ansN;
for(int i=0;i<7;i++)limit*=10;
S s1,s2;
double a,ans=0;
for(int i=3;i<limit;i+=2){
a=CustomPhi(i);
if(a==1)continue;
s1.set(i);
s2.set(a);
if(s1==s2){
if(ans==0||ans>i/a){
ans=i/a;
ansN=i;
}
}
}
printf("%lf ans=%d time=%lf",ans,ansN,clock()-start);
}
