「オイラー1～10」の編集履歴（バックアップ）一覧に戻る

オイラー1～10 - (2012/08/25 (土) 07:36:54) の編集履歴(バックアップ)

---

オイラープロジェクトという数学の練習問題を解くサイト。
プログラムで解いても数式で解いてもいいらしい。
http://projecteuler.net/about

問い２

フィナボッチ数のうち４００万以下の偶数の和を求める問題。
もしかしたら大きな数になるかと思ったら意外と小さい数になった。
フィナボッチ数の性質を考えたら当たり前か。
偶数項だけ見て小さい順にＡiとラベルを張っていくとAi=4*(Ai-1)+Ai-2という性質があることを利用して計算量を下げる。
出題側としてはこの数式の性質を考えてほしいのだろうと思うが、私はプログラムが書けただけで満足してしまってる。

#include<stdio.h>
int main(){
__int64 sum=2,add=0,now=2,t;
while(1){
	t=now*4+add;
	if(t>=4000000)break;
	sum+=t;
	add=now;
	now=t;
}
printf("%lld\n",sum);
}

問い３

競技プログラムではないし計算量も小さいので適当な計算と出力で解く。
きっと問題Ｎｏがあがったらこんな簡単にはいかないんだろうな。

#include<stdio.h>
int main(){
__int64 a=600851475143,b=775147;
while(b>1){
	while(a%b!=0&&b!=1)b--;
	printf("%lld\n",b);
	a=b;
	b--;
}
}

問い4

３桁の数を２つ掛け算した結果回文数になってる数のうち最大の数を求める問題。
私の頭の悪さを証明するようなコードでアセプト。

#include<stdio.h>
#include<algorithm>
#include<vector>
bool isRe(int num){
if(num<=100000){
	return false;
}
char cs[7];
for(int i=0;i<6;i++){
	cs[i]=num%10;
	num/=10;
}
bool ok=true;
for(int i=0;i<3;i++)ok=ok&&(cs[i]==cs[5-i]);
return ok;
}
int main(){
int t;
std::vector<int> res;
for(int i=100;i<1000;i++){
	for(int j=100;j<1000;j++){
		t=i*j;
		if(isRe(t))res.push_back(t);
	}
}
std::sort(res.begin(),res.end());
for(int i=0;i<res.size();i++){
	printf("%d ",res[i]);
}
}