「プロジェクトオイラー問い41～50」の編集履歴（バックアップ）一覧に戻る
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.
解法
９桁や８桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは８桁と９ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。
よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。
末尾の数字が２の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。
#include<stdio.h>
#include<stdlib.h>
bool spents[10]={true,false,false,false,false,false,false,false,false,false};
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool isPandigital(int n,int keta){
for(int i=0;i<keta;i++){
if(n%10>keta)return false;
n/=10;
}
return true;
}
void saiki(int n,int keta){
if(isPrime(n)&&isPandigital(n,keta)==true&&ans<n){
ans=n;
}
if(7<=keta)return;
for(int i=1;i<=7;i++){
if(spents[i]==false){
spents[i]=true;
saiki(n*10+i,keta+1);
spents[i]=false;
}
}
}
int main(){
saiki(0,0);
printf("%d",ans);
}
*問い42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
ファイルから単語を読み取り、それを数字に置き換えた時三角数になるかどうか調べる問題。
解法
単語を一つずつ読み込んで数字を計算するだけです。
実はＣの処理系ではアルファベットが連続していることは保証されてないのでtoHash関数は実はインチキ関数なのですが、ま手元の環境では連続しているし連続してないことが超レアケースなので気にしません。
スクリプトなら物凄く短く記述できる可能性があります。
一気にデータを読んでスプリットして、それを一気に処理して結果を返す関数に入れて条件を満たすものをカウントさせれば一行で記述が済むかも。
#include<stdio.h>
#include<stdlib.h>
#include<set>
int toHash(char *text){
int re=0;
for(int i=0;text[i]!='\0';i++){
re+=text[i]-'A'+1;
}
return re;
}
int main(){
int ans=0,sum=0;
std::set<int> memo;
for(int i=1;i<50;i++){
sum+=i;
memo.insert(sum);
}
FILE *fp;
if ((fp = fopen("euler42Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
char text[100],c;
while(1){
fscanf(fp,"\"%[^\"]\"",text);
if(fscanf(fp,"%c",&c)==EOF)break;
if(memo.find(toHash(text))!=memo.end())ans++;
}
fclose(fp);
printf("ans=%d",ans);
}
*問い43
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
解法
再帰関数で全部試すだけです。
先頭桁0が許されるかは不明ですが先頭桁0でこの条件を満たす数はないようです。
#include<stdio.h>
#include<iostream>
bool spents[10]={false,false,false,false,false,false,false,false,false,false};
int mask=1000;
int mod[]={2,3,5,7,11,13,17};
__int64 ans=0;
void saiki(int n,int keta,__int64 num){
if(keta>=4){
if(n%mod[keta-4]!=0)return ;
}
if(keta==10){
ans+=num;
}else{
for(int i=0;i<=9;i++){
if(spents[i]==false){
spents[i]=true;
saiki((n*10+i)%mask,keta+1,num*10+i);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
std::cout<<"ans="<<ans;
}
*問い44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
二つの五角数の和と差がともに５角数になるとき差の最小値を求めよという問題。
解法
とりあえず小さい方から全組み合わせを検討するコードを書いてみました。
もちろんこんなコードで速度が出るはずもなくＣ++で４秒もかかっています。
どうしたら速度が出るか、ちょっと考えあぐねています。
変数の数が３つになるとけっこう悩むものです。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
bool is5(__int64 m){
__int64 m1=sqrt(1+24*m);
return m1*m1==1+24*m && (1+m1)%6==0;
}
int main(){
__int64 ans=0,n1,n2;
double start=clock();
for(__int64 a=2;;a++){
if(ans!=0&&6*a-4>ans)break;
n1=a*(3*a-1)/2;
for(__int64 b=a-1;b>0;b--){
n2=b*(3*b-1)/2;
if(ans!=0&&n1-n2>=ans)break;
if(is5(n1+n2)&&is5(n1-n2)){
ans=n1-n2;
std::cout<<"("<<n1<<" "<<a<<" "<<n2<<" "<<b<<")";
}
}
}
std::cout<<"ans="<<ans<<" time="<<clock()-start;
}
*問い45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
解法
特に賢い解法を思いつかなかったので、三角数、5角数、６角数を求め、ループの中で３つの数のうち一番小さい数になったものだけをインクリメントしていきます。
そうすると答えがあればきちんとそろうわけです。
#include<stdio.h>
#include<iostream>
int main(){
__int64 t=285+1,p=165,h=143,t1,p1,h1;
while(1){
t1=(t*(t+1))/2;
p1=(p*(3*p-1))/2;
h1=(h*(2*h-1));
if(t1==p1&&t1==h1)break;
if(t1<=p1&&t1<=h1)t++;
if(p1<=t1&&p1<=h1)p++;
if(h1<=t1&&h1<=p1)h++;
}
std::cout<<t1;
}
