「プロジェクトオイラー問い51～60」の編集履歴（バックアップ）一覧に戻る
*問い51
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2051
*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万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタンを求めてその出現回数をカウントしてみました。
答えは正しいですし34秒で答えは出るのですが何か間違ったコードを書いてる感がすごくあります。
Ｃ++なら遅くても数秒程度で答えが出るコードが正しいコードのような気がします。
答えはもっとシンプル。
そんな気がするのでこの問題後日再チャレンジする予定です。
#include<stdio.h>
#include<map>
#include<string>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<set>
struct S{
int num,count;
};
std::set<std::string> patternSet;
std::map<std::string,S> memo;
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
void setMemo(char text[10],char num,int p,int n){
if(p==0)patternSet.clear();
if(num!=-1){
if(patternSet.find(text)==patternSet.end()){
patternSet.insert(text);
if(memo.find(text)==memo.end()){
S s;
s.count=1;
s.num=n;
memo[text]=s;
}else{
memo[text].count++;
}
}
}
if(text[p]=='\0')return;
if(num==-1){
setMemo(text,-1,p+1,n);
char c=text[p];
text[p]='*';
setMemo(text,c,p+1,n);
text[p]=c;
}else{
setMemo(text,num,p+1,n);
if(text[p]==num){
text[p]='*';
setMemo(text,num,p+1,n);
text[p]=num;
}
}
}
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;
}
}
}
int main(){
setSo();
int num;
std::string str,str2;
for(int i=0;i<sosuu.size();i++){
int p=sosuu[i];
char text[10];
sprintf(text,"%d",p);
setMemo(text,-1,0,p);
//std::cout<<"\n";
}
int ans=up+1;
std::cout<<memo["56**3"].count<<"\n";
for(std::map<std::string,S>::iterator it=memo.begin();it!=memo.end();it++){
if((*it).second.count==8&&ans>(*it).second.num){
ans=(*it).second.num;
}
}
printf("%d",ans);
}
*問い52
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2052
解法
この問題は本当はコードを書くまでもなく1/7の性質について知っていたら簡単に解ける問題です。
一応コードを書いてみました。
#include<stdio.h>
int main(){
for(int i=2;i<10;i++){
int memo[7],num=1,count[10]={0};
bool ok=true;
for(int j=0;j<6;j++){
num*=10;
memo[j]=num/i;
num%=i;
if(count[num]==1)ok=false;
count[num]++;
}
if(num==1&&ok==true){
for(int j=0;j<6;j++)printf("%d",memo[j]);
break;
}
}
}
*問い53
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2053
パスカルの三角形を101段目まで書いたとき、100万を超える項は何個あるかという問題です。
解法
パスカルの三角形を計算して１００万以上になったらその影響下にある項は全て１００万で統一して計算するのが一番シンプルですが、それもいいのですが無意味に計算量を抑えて遊んでみました。
一段ずつ上からパスカルの三角形に基づき計算します。
左端から計算して100万を超えたらそこより右は計算しないでその段の残りの項の数からその段の100万を超えた項の数を求め次の段へ計算をすすめます。
この手法なら問題が100000段とかになっても計算量がそんなに増えない程度しか利点がありません。
１段目0Ｃ0から計算が始まるので100Ｃｒだと101段目まで計算する点に注意するくらいです。
#include<stdio.h>
#include<string.h>
#include<time.h>
int main(){
double start=clock();
int memo[102]={0,1,0},ans=0;
for(int n=1;n<=101;n++){
int next[102]={0};
int r;
for(r=1;r<=n;r++){
next[r]=memo[r-1]+memo[r];
if(next[r]>=1000*1000)break;
}
if(r<n){
if(n%2==0){
ans+=(n/2-r+1)*2;
}else{
ans+=(n+1)/2==r?1:1+((n+1)/2-r)*2;
}
}
memcpy(memo,next,sizeof(next));
}
printf("ans=%d time=%lf",ans,clock()-start);
}
*問い54
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2054
２人対戦のポーカーの手札が１０００勝負分与えられるのでプレーヤＡの勝った回数を答えよという問題。、
解法
役を判定する関数を全部書いて大きい役からチェックしスコアを算出してみました。
役の中で一番大きな数字をスコアに加算することでコードを少し簡略化したつもりです。
役の排他性を考えたポーカーの考案者は中々素晴らしいものがありますね。
スートで判定するということがないのでコードは少し簡単です。
#include<stdio.h>
#include<algorithm>
struct CARD{
int num;
char suit;
void set(char text[3]){
if(text[0]=='T'){
num=10;
}else if(text[0]=='J'){
num=11;
}else if(text[0]=='Q'){
num=12;
}else if(text[0]=='K'){
num=13;
}else if(text[0]=='A'){
num=14;//1は一番大きな数として扱う
}else{
num=text[0]-'0';
}
suit=text[1];
}
bool operator<(const CARD& c)const{
if(c.num!=num)return num<c.num;
return suit<c.suit;
}
};
CARD cardsA[5],cardsB[5];
int onePairs(CARD cards[5]){
int point=1000;
for(int i=0;i<4;i++){
if(cards[i].num==cards[i+1].num)return point+cards[i].num;
}
return 0;
}
int TwoPairs(CARD cards[5]){
int point=2000;
if(cards[0].num==cards[1].num){
if(cards[2].num==cards[3].num){
return point+cards[3].num;
}
if(cards[3].num==cards[4].num){
return point+cards[3].num;
}
}
if(cards[1].num==cards[2].num&&cards[3].num==cards[4].num){
return point+cards[3].num;
}
return 0;
}
int ThreeOfAKind(CARD cards[5]){
int point=3000;
if(cards[0].num==cards[2].num||cards[1].num==cards[3].num||cards[2].num==cards[4].num){
return point+cards[2].num;
}
return 0;
}
int Straight(CARD cards[5]){
int point=4000;
int num=cards[0].num;
for(int i=1;i<5;i++){
num++;
if(cards[i].num!=num)return 0;
}
return point+cards[4].num;
}
int flash(CARD cards[5]){
int point=5000;
if(cards[0].suit==cards[1].suit&&cards[1].suit==cards[2].suit&&cards[2].suit==cards[3].suit&&cards[3].suit==cards[4].suit){
return point+cards[4].num;
}
return 0;
}
int FullHouse(CARD cards[5]){
int point=6000;
if(cards[0].num==cards[1].num&&cards[2].num==cards[4].num)return point+cards[2].num;
if(cards[0].num==cards[2].num&&cards[3].num==cards[4].num)return point+cards[3].num;
return 0;
}
int FourOfAKind(CARD cards[5]){
int point=7000;
if(cards[0].num==cards[3].num){
return point+cards[0].num;
}
if(cards[1].num==cards[4].num){
return point+cards[1].num;
}
return 0;
}
int StraightFlush(CARD cards[5]){
int point=8000;
if(flash(cards)!=0&& Straight(cards)!=0){
return point+cards[4].num;
}
return 0;
}
int RoyalFlush(CARD cards[5]){
int point=9000;
if(flash(cards)!=0&&cards[0].num==10&&cards[1].num==11&&cards[2].num==12&&cards[3].num==13&&cards[4].num==14){
return point+14;
}
return 0;
}
int calc(CARD cards[5]){
int point;
if((point=RoyalFlush(cards))!=0)return point;
if((point=StraightFlush(cards))!=0)return point;
if((point=FourOfAKind(cards))!=0)return point;
if((point=FullHouse(cards))!=0)return point;
if((point=flash(cards))!=0)return point;
if((point=Straight(cards))!=0)return point;
if((point=ThreeOfAKind(cards))!=0)return point;
if((point=TwoPairs(cards))!=0)return point;
if((point=onePairs(cards))!=0)return point;
return 0;
}
int lastCheck(CARD cardsA[5],CARD cardsB[5]){
for(int i=4;i>=0;i--){
if(cardsA[i].num>cardsB[i].num)return 1;
if(cardsA[i].num<cardsB[i].num)return -1;
}
return 0;
}
void print(CARD cards[5]){
printf("(");
for(int i=0;i<5;i++)printf("%d%c ",cards[i].num,cards[i].suit);
printf(")");
}
int main(){
char c[3],c1;
int ans=0;
while(1){
bool last=false;
for(int i=0;i<5;i++){
if(scanf("%s",c)==EOF){
last=true;
break;
}
cardsA[i].set(c);
}
if(last==true)break;
for(int i=0;i<5;i++){
scanf("%s",c);
cardsB[i].set(c);
}
std::sort(cardsA,cardsA+5);
std::sort(cardsB,cardsB+5);
//print(cardsA);
//print(cardsB);
int p1=calc(cardsA);
int p2=calc(cardsB);
//printf("(%d %d)\n",p1,p2);
if(p1==p2)p1+=lastCheck(cardsA,cardsB);
if(p1>p2)ans++;
}
printf("ans%d",ans);
}
*問い55
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2055
10000未満のLychrel数はいくつあるか?
解法
定義通り素朴に計算してみました。
(defun toRev(n)
(parse-integer (reverse (princ-to-string n))))
(let ((a) (ans 0))
(dotimes (i 9999)
(setq a (+ 1 i))
(dotimes (j 50)
(setq a (+ a (toRev a)))
(if (= a (toRev a))
(setq ans (+ ans 1) j 50)
)))(- 9999 ans))
*問い56
a^b (a,b＜100の自然数)として各桁の和の最大値を求めよ。
解法
Lispで力づくで解いてました。
賢い方法ありますかね、これ。
(defun ketaSum(n)
(apply #'+ (map 'list #'digit-char-p (princ-to-string n))))
(let ((ans 0) (a 0))
(dotimes (i 99)
(dotimes (j 99)
(setq a (ketaSum (expt (+ 1 i) (+ 1 j))))
(if (< ans a)
(setq ans a)
)))ans)
*問い57
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2057
２の平方根を連分数で表したとき、連分数の項によっては分子の方が分母より桁数が多くなる。
１０００項目までで分子の方が大きい項の数を数えよ。
解法
数式をそのまま再帰式になおすだけです。
saikl関数が数式を表します。
一番底が5/2で始まり再帰を戻るたびに項が大きくなっていきます。
(defvar ans 0)
(defun saiki(deep)
(let ((a 0) (re 0))
(if (= deep 1000)
(setq a (/ 5 2))
(setq a (+ 2 (/ 1 (saiki (+ 1 deep))))))
(setq ans (+ ans (check (- a 1))))a))
saiki
(defun check (n) (let ((a (numerator n))
(b (denominator n))
(re 0))
(if (< (length (princ-to-string b)) (length (princ-to-string a)))
(setq re 1)
(setq re 0))re))
saiki
(defun main()
(setq ans 0)
(saiki 0) ans)
(main )
*問い58
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2058
渦巻きに配置された格子の対角線上にある素数の数を調べ上げよ
解法
なにやらみなさん色々凝ったコードを書いているようですが素朴に計算しても十分速度的に間に合います。
#include<stdio.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
int all=0,count=0,size=3,num=1;
while(1){
for(int i=0;i<4;i++){
num+=size-1;
if(isPrime(num)==true)count++;
}
all+=4;
if(count*10<=all)break;
size+=2;
}
printf("%d",size);
}
*問い60
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060
素数3, 7, 109, 673は非凡な性質を持っている. 任意の2つの素数を任意の順で繋げると, また素数になっている. 例えば, 7と109を用いると, 7109と1097の両方が素数である. これら4つの素数の和は792である. これは, このような性質をもつ4つの素数の組の和の中で最小である.
任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.
解法
全然だめです、賢い解法思いつきません。
素数を点、結合可能な素数の組を線からなるグラフとみて、３万以下の素数についてグラフが五望星をなしている場所を探索で探してみましたがコードは膨らむし速度は出ないしで駄目ですね。
グラフの生成部分が物凄く遅くｃ++なのに答えを出すのに34秒もかかってます。
こんなコードではプロジェクトオイラーでは負け組みな気がします。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<map>
#include<stdlib.h>
#include<set>
#include<string.h>
#include<string>
#include<time.h>
const int up=100000;
std::vector<__int64> sosuu;
bool isPrime[up+1];
std::map<int,std::set<int> > cons;
int ans=0;
void setPrime(){
int i2;
memset(isPrime,true,sizeof(isPrime));
isPrime[0]=isPrime[1]=false;
for(int i=4;i<=up;i+=2)isPrime[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(isPrime[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
isPrime[j]=false;
}
}
}
bool checkPrime(__int64 n){
if(n<2)return false;
for(int i=0;sosuu[i]*sosuu[i]<=n;i++){
if(n%sosuu[i]==0)return false;
}
return true;
}
void setConnect(){
char text[20];
__int64 a,b;
for(int i=0;sosuu[i]<=30000;i++){
for(int j=i+1;sosuu[j]<=30000;j++){
sprintf(text,"%I64lld%I64lld",sosuu[i],sosuu[j]);
sscanf(text,"%I64lld",&a);
sprintf(text,"%I64lld%I64lld",sosuu[j],sosuu[i]);
sscanf(text,"%I64lld",&b);
if(checkPrime(a)==true&&checkPrime(b)==true){
cons[sosuu[i]].insert(sosuu[j]);
}
}
}
}
bool addOK(std::set<int>& perm,int addNum){
for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
if(cons[(*it)].find(addNum)==cons[(*it)].end())return false;
}
return true;
}
void print(std::set<int> perm,int num){
printf("解候補の組(%d ",num);
for(std::set<int>::iterator it=perm.begin();it!=perm.end();it++){
printf("%d ",(*it));
}
printf(")\n");
}
void saiki(int num,std::set<int>::iterator it,int count,int wa,std::set<int>& perm){
if(ans!=0&&ans<=wa)return;
if(count==4){
print(perm,num);
ans=wa;
return;
}
int wa2;
if(count!=0)it++;
for(;it!=cons[num].end();it++){
if(addOK(perm,(*it))==true){
wa2=wa+(*it);
perm.insert(*it);
saiki(num,it,count+1,wa2,perm);
perm.erase(*it);
}
}
}
int main(){
double start=clock();
setPrime();
printf("処理0終了\n");
setConnect();
printf("処理１終了 サイズ%d\n",cons.size());
std::set<int> perm;
for(std::map<int,std::set<int> >::iterator it=cons.begin();it!=cons.end();it++){
if((*it).second.size()>3)saiki((*it).first,(*it).second.begin(),0,(*it).first,perm);
}
printf("\nans=%d time=%lf",ans,clock()-start);
}
