「オイラープロジェクト51～60」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト51～60 - (2012/10/10 (水) 10:00:51) のソース
*問い50
連続した素数の和として表される１００万以下の素数のうち和の長さが最長になる数を求めよという問題。
素数のみという条件が意外と手ごわい問題。
この条件がなければ簡単な尺取り虫アルゴリズムで片がつくんだけどな、、、
とりあえず力づくの全探索に近い手法で解いたけどかなり工夫の余地がありそうな問題。
#include<stdio.h>
#include<string.h>
#include<vector>
const int up=1000001;
bool so[up];
int memo[up];
std::vector<__int64> sosuu;
void setSo(){
int i2;
__int64 add=2;
memset(so,true,sizeof(so));
sosuu.push_back(0);
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
add+=i;
sosuu.push_back(add);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
int main(){
setSo();
memset(memo,0,sizeof(memo));
int ans=0,len=0;
__int64 t;
for(int i=0;i<sosuu.size();i++){
for(int j=0;j<i;j++){
if(i-j<=len)break;
t=sosuu[i]-sosuu[j];
if(t>=up||(t>2&&t%2==0))continue;
if(so[(int)t]==true){
len=i-j;
ans=t;
}
}
}
printf("%d %d",ans,len);
}
*問い51
*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)
解法
特に賢い方法を思いつかなかったので100万以下で全探索してみた。
私のパソコンで15秒。
この問題が作られた年度のパソコンの性能を考えたら少し遅いかもしれない。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<string.h>
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
std::map<std::string,int> mins,count;
int ansCount[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
void saiki(std::string& str,char num,int deep,int n){
if(str.size()==deep){
if(mins.find(str)==mins.end()){
mins[str]=n;
count[str]=1;
}else{
count[str]++;
ansCount[mins[str]]=count[str];
}
}else{
if(str[deep]==num){
str[deep]='*';
saiki(str,num,deep+1,n);
str[deep]=num;
}
saiki(str,num,deep+1,n);
}
}
void calc(int num){
std::string str="",str2="";
int n=num;
while(num!=0){
str+=(num%10+'0');
num/=10;
}
std::reverse(str.begin(),str.end());
for(int i='0';i<='9';i++){
saiki(str,i,0,n);
}
}
int main(){
setSo();
memset(ansCount,0,sizeof(ansCount));
for(int i=0;i<sosuu.size();i++){
calc(sosuu[i]);
}
int ans;
for(ans=1;ans<up;ans++){
if(ansCount[ans]==8)break;
}
printf("%d",ans);
}
*問い52
125874を2倍すると251748となる. これは元の数125874と同じ数を含む.
2x, 3x, 4x, 5x, 6xがxと同じ数を含むような最小の正整数xを求めよ.
数字一つの確認コストが高くないので一つずつ全探索してみる。
数字が大きくなったらもう一工夫が必要。
例えば先頭桁は1意外認められないとか。
#include<stdio.h>
bool check(int p1,int p2){
int count[10]={0};
while(p1!=0){
count[p1%10]++;
p1/=10;
}
while(p2!=0){
count[p2%10]--;
p2/=10;
}
bool ok=true;
for(int i=0;i<10;i++)ok=(ok&&(count[i]==0));
return ok;
}
int main(){
for(int i=1;i<1000000;i++){
//とりあえず100万まで試しにさがしてみる。
bool ok=true;
for(int j=2;j<7;j++){
if(check(i,i*j)==false){
ok=false;
break;
}
}
if(ok==true){
for(int j=1;j<7;j++){
printf("%d ",j*i);
}
printf("\n");
}
}
}
*問い53
nCr (n=1...100)の時100万を超えるnCrは何個あるか？
パスカルの三角形であるポイントの値が１００万を超えたらどんな値だろうがその位置の影響下にある下の段の数字は全部１００万を超えます。
これを利用して１００万以上を特別扱いして値あふれを防ぎます。
どの問題ももっと賢い方法が幾らでもありそうなのがオイラープロジェクトのサイトの特徴のようです。
#include<string.h>
int main(){
int memo[102][102];
memset(memo,0,sizeof(memo));
int mymax=1000000,ans=0;
for(int i=1;i<101;i++){
memo[i-1][0]=1;
for(int j=0;j<=i;j++){
memo[i][j]=memo[i-1][j];
if(j>0)memo[i][j]+=memo[i-1][j-1];
if(memo[i][j]>mymax){
memo[i][j]=mymax+1;
ans++;
}
//printf("%d ",memo[i][j]);
}
//printf("\n");
}
printf("%d",ans);
}
*問い54
ポーカーの役を判定するプログラムを書いてみたけど。
ストレートは10,11,12,13、Ａを含むのか？
両者ワンペアかツーペア同じ数字の場合、スートを使って比べないといけない場合を忘れていたのでコード全部書き直しになってる。
ワンペア、ツーペア、ストレート、フルハウス、ストレートフラッシュの場合でこの場合が必要になるので全面書き直し、ポーカーの判定は意外とめんどくさいな。
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
int type[4];//カードのスートのそろい具合
int card[5];//カードの数字
int StraightFlashOrRoyalFlash(){
//とか
int base=9000;//4桁目役の種類、３桁目スートの順位、２,1桁目最大カードの数字
int s=-1;
for(int i=0;i<4;i++)if(type[i]==5)s=i;
if(s==-1)return s;
base+=s*100;
//カードの数字はソート済みで与えれる
if(card[0]==1&&card[1]==10&&card[2]==11&&card[3]==12&&card[4]==13){
return base;
}
//ストレートフラッシュか
base=8000+s*100;
for(int i=1;i<5;i++){
if(card[i-1]+1!=card[i])return -1;
}
return base+card[4];
}
int fourCard(){
int base=7000;
//カードはソート済みで与えられる
if(card[0]==card[3])return base+card[0];
if(card[1]==card[4])return base+card[1];
return -1;
}
int fullHouse(){
int base=6000;
//カードはソート済み
if(card[0]==card[2]&&card[3]==card[4])return base+card[3];
if(card[0]==card[1]&&card[2]==card[4])return base+card[2];
return -1;
}
int flash(){
int base=5000;
for(int i=0;i<4;i++){
if(type[i]==5)return base+i*100+card[4];
}
return -1;
}
int Straight(){
int base=4000;
for(int i=1;i<5;i++){
if(card[i-1]+1!=card[i])return -1;
}
return base+card[4];
}
int threeCard(){
int base=3000;
if(card[0]==card[2])return base+card[0];
if(card[1]==card[3])return base+card[1];
if(card[2]==card[4])return base+card[2];
return -1;
}
int twoPareOrOnePare(){
int base=2000;
int count[14]={0};
for(int i=0;i<5;i++){
count[card[i]]++;
}
int sum=0,mc;
for(int i=1;i<14;i++){
if(count[i]==2){
sum++;
mc=i;
}
}
if(sum==2){
return base+mc;
}
base=1000;
if(sum==1){
return base+mc;
}
return -1;
}
int readToScore(){
memset(type,0,sizeof(type));
}
int main(){
}
*問い55
47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.
全ての数が素早く回文数になるわけではない. 349を考えよう,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
349は, 3回の操作を経て回文数になる.
回文数にたどり着かない数をLychrel数とする。
10000以下の数は５０回未満の操作で回文数になるか、５０回以上で Lychrel数と仮に分類しておくかである。
10000以下のLychrel数の数を数えよ。
4994は回文数だが一回目の操作以降回文数にたどり着かないので回文数かつLychrel数と分類される。
とりあえず愚直に実装してみたけど少し速度が遅い。
うーんもう少し賢い実装方法がありそう。
まあちょっとだけ巨大な数を扱ったが流石Ｌｉｓｐだ何ともないぜ。
(defun rev (n re)
(if (= n 0)
re
(rev (floor (/ n 10)) (+ (mod n 10) (* re 10)))))
rev
(defun calc (n deep)
(let ((next (+ n (rev n 0))))
(if (< 49 deep) 1
(if (= next (rev next 0)) 0
(calc next (+ deep 1))))))
calc
(let ((sum 0))
(dotimes (i 10000 sum)
(setq sum (+ sum (calc (+ i 1) 1)))))
*問い56
Googol (10^100)は非常に大きな数である: 1の後に0が100個続く. 100^100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.
a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.
Ｌｉｓｐの整数処理能力にものを言わせてゴリ押しで全探索。
もう少し賢い方法がありそうだけど思いつかないな。
(defun sum (n wa)
(if (= n 0) wa
(sum (floor (/ n 10)) (+ wa (mod n 10)))))
sum
(let ((max 0))
(dotimes (a 100 max)
(dotimes (b 100 max)
(let ((c (sum (expt (+ a 1) (+ 1 b)) 0)))
(if (< max c)
(setq max c)
0)))))
*問い57
2の平方根は無限に続く連分数で表すことができる.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.
最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?
Ｌｉｓｐの分数処理能力にものを言わせて愚直に計算します。
おそらく数式を使うのが賢いのだとは思いますが。
(defun keta (n deep)
(if (= n 0) deep
(keta (floor (/ n 10)) (+ 1 deep))))
(defun calc (deep k)
(if (<= k deep) (+ 2 (/ 1 2))
(+ 2 (/ 1 (calc (+ 1 deep) k)))))
(let ((n 3/2) (a 0) (b 0) (ans 0))
(dotimes (i 999 ans)
(setq n (+ 1 (/ 1 (+ 1 n))))
(setq a (keta (numerator n) 0) b (keta (denominator n) 0))
(if (< b a)
(setq ans (+ ans 1))
)))
*問い58
1から始めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≈ 62%である.
渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.
#include<stdio.h>
#include<vector>
#include<iostream>
bool isSo(int n){
if(n==2)return true;
if(n%2==0)return false;
for(int i=3;i*i<=n;i+=2){
if(n%i==0)return false;
}
return true;
}
int main(){
__int64 p=0,all;
int sum=1,i=1;
while(1){
all=1+i*4;
for(int k=0;k<4;k++){
sum+=i*2;
p+=isSo(sum);
}
//std::cout<<all<<" "<<p<<" "<<2*i+1<<"\n";
//if(i>5)break;
if(all>p*10){
std::cout<<all<<" "<<p<<" "<<i*2+1;
break;
}
i++;
}
}
*問い59
(訳者注: 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている.
モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である. 65 XOR 42 = 107であり, 107 XOR 42 = 65である.
破られない暗号化のためには, 鍵は平文と同じ長さのランダムなバイト列でなければならない. ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある. また, もし一方が失われると, 暗号文を復号することは不可能になる.
悲しいかな, この手法はほとんどのユーザーにとって非現実的である. そこで, 鍵の変わりにパスワードを用いる手法が用いられる. パスワードが平文より短ければ (よくあることだが), パスワードは鍵として繰り返し用いられる. この手法では, 安全性を保つために十分長いパスワードを用いる必要があるが, 記憶するためにはある程度短くないといけない.
この問題での課題は簡単になっている. 暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.
*解法
よく使う単語というので、どんな単語がいいのか悩んだものの解いてみたら意外と簡単でした。
最後は英文として意味が通るかの目視確認が必要なのかと思って覚悟してたのですが。
2単語チェックするだけで解けました。
#include<stdio.h>
#include<string>
int main(){
std::string str,str2;
int c;
char sp,c1;
FILE *fp; /* (1)ファイルポインタの宣言 */
fp = fopen("euler59data.txt", "r");
while(fscanf(fp,"%d%c",&c,&sp)!=EOF){
str+=(char)c;
}
fclose(fp);
char key[4],k;
str2=str;
char words[2][6]={"that","this"};
for(key[0]='a';key[0]<='z';key[0]++){
for(key[1]='a';key[1]<='z';key[1]++){
for(key[2]='a';key[2]<='z';key[2]++){
for(int i=0;i<str.size();i++){
str2[i]=(str[i]^key[i%3]);
}
bool ok=true;
for(int i=0;i<2;i++){
if(str2.find(words[i],0)==std::string::npos){
ok=false;
}
}
int ans=0;
if(ok==true){
printf("\n%s\n",str2.c_str());
for(int i=0;i<str2.size();i++){
ans+=(int)str2[i];
}
printf("%d\n",ans);
}
}
}
}
}
*問い60
素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の組の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.
*解法
マシンパワーにものを言わせた強引な解き方でアセプト。
何せ1億までの配列を用意して解いてるんだからこれは強引。
もし1億で足らなかったら、素数のみ検証するアルゴリズムに変更する必要があった。
1億以内で済んでよかった。
1億までの素数の集合をいつもの篩で求めて、後は素数を２つにわった両方の数が条件を満たすか調べて最後はグラフの探索に帰着して解いてみた。
結構面白い問題だった。
うーんとりあえず実装のしやすさを基準にアルゴリズムを選んだけれど1万以下の素数から合成した数が素数か調べた方がメモリ的にも速度的にも有利かもしれない。
素数まばらだし。
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
const int up=100000000;
std::vector<int> sosuu;
bool so[up+1];
std::map<int,std::set<int> > G;
int ans=up*10,ansPerm[5];
const int size=8;
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
void setCut(int num){
int L,R,n;
int base[]={1,10,100,1000,10000,100000,1000000,10000000};
int m=size;
for(int i=1;i<size;i++){
if(num<base[i]){
m=i;
break;
}
}
for(int i=1;i<m;i++){
L=num/base[i];
R=num%base[i];
if(R<base[i-1])continue;
if(so[L]==false||so[R]==false)continue;
if(so[R*base[m-i]+L]==false)continue;
if(L==R)continue;
G[L].insert(R);
G[R].insert(L);
}
}
void saiki(int deep,int wa,int num,int perm[5]){
if(wa>ans)return;
for(int i=0;i<deep;i++){
if(G[num].find(perm[i])==G[num].end()){
return ;
}
}
if(deep==4){
if(wa<ans){
ans=wa;
memcpy(ansPerm,perm,sizeof(ansPerm));
}
}else{
std::set<int>::iterator it;
for(it=G[num].upper_bound(num);it!=G[num].end();it++){
perm[deep+1]=(*it);
saiki(deep+1,wa+(*it),(*it),perm);
}
}
}
int main(){
setSo();
for(int i=0;i<sosuu.size();i++){
setCut(sosuu[i]);
}
std::map<int,std::set<int> >::iterator it;
std::vector<int> dell;
for(it=G.begin();it!=G.end();it++){
if((*it).second.size()<4){
dell.push_back((*it).first);
}
}
for(int i=0;i<dell.size();i++){
G.erase(dell[i]);
}
int perm[5];
for(it=G.begin();it!=G.end();it++){
perm[0]=(*it).first;
saiki(0,(*it).first,(*it).first,perm);
}
printf("%d",ans);
for(int i=0;i<5;i++){
printf(" %d",ansPerm[i]);
}
}
