※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問い21~30」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問い21~30 - (2012/12/17 (月) 18:57:34) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *問い21
 d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
 もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
 例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
 また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
 それでは10000未満の友愛数の和を求めよ.
 
 解法
 コードの中では1~nまでの約数を求める計算はsetYakusuu関数で簡単に方がついてます。
 後は条件を満たすかどうかmain関数のなかで調べるだけです。
 
 
  #include<stdio.h>
  const int up=10000;
  int memo[up+1]={0};
  void setYakusuu(){
 	for(int i=1;i<=up;i++){
 		for(int j=2*i;j<=up;j+=i){
 			memo[j]+=i;
 		}
 	}
  }
  
  
  int main(){
 	setYakusuu();
 	int d,ans=0;
 	for(int i=2;i<up;i++){
 		d=memo[i];
 		if(d<up&&memo[d]==i&&d!=i){
 			printf("%d %d\n",d,i);
 			ans+=i;
 		}
 	}
 	printf("%d",ans);
  }
 
 
 
 
 
 
 
 
 *問い22
 5000個以上の名前が書かれている46Kのテキストファイル names.txt を用いる. まずアルファベット順にソートせよ.
 のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.
 たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ.
 ファイル中の全名前のスコアの合計を求めよ.
 
 解法
 この問題回答者が二つのグループに分かれる気がします。
 テキスト処理が得意なスクリプト言語の性能を最大限に引き出し数行のコードで問題を解く人と普通に30行程度使って解く人です。
 私はC++で解いてるので後者です。
 C++でもコードを工夫すれば短くなるかな?
 
 
 
  #include<stdio.h>
  #include<stdlib.h>
  #include<vector>
  #include<string>
  #include<algorithm>
  int main(){
 	FILE *fp;
 	char name[256],c;
 	std::string strName;
 	if((fp=fopen("euler22Data.txt","r"))==NULL){
 		printf("file open Error");
 		exit(EXIT_FAILURE);
 	}
 	std::vector<std::string> names;
 	while(1){
 		fscanf(fp,"\"%[^\"]\"",name);
 		names.push_back(name);
 		if(fscanf(fp,"%c",&c)==EOF)break;
 	}
 	std::sort(names.begin(),names.end());
 	int ans=0;
 	for(int i=0;i<names.size();i++){
 		strName=names[i];
 		int sum=0;
 		for(int j=0;j<strName.size();j++){
 			sum+=strName[j]-'A'+1;
 		}
 		ans+=sum*(i+1);
 	}
 	fclose(fp);
 	printf("%d",ans);
  }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 *問い23
 ある数mはmの倍数になる数は全てmを約数に持ちます、つまりmの倍数の約数の和にはすべてmを足しておくといいわけです。
 これを利用してsetKazyousuu関数のなかで約数の和をmemoに入れていきます。
 計算を高速化するために過剰数になった数だけmemo[i]=-1と入れておきます。
 後はmainループの中で過剰数を調べればコード実行時間0.016秒となります。
 
 
  #include<stdio.h>
  #include<stdio.h>
  #include<vector>
  #include<time.h>
  const int up=28123;
  int memo[up+1]={0};
  std::vector<int> kazyou;
  void setKazyousuu(){
 	for(int i=1;i<=up;i++){
 		if(i<memo[i]){
 			kazyou.push_back(i);
 			memo[i]=-1;
 		}
 		for(int j=2*i;j<=up;j+=i){
 			memo[j]+=i;
 		}
 	}
  }
  int main(){
 	double start=clock();
 	setKazyousuu();
 	int k,ans=0;
 	for(int i=1;i<up;i++){
 		bool ok=true;
 		for(int j=0;j<kazyou.size()&&2*kazyou[j]<=i;j++){
 			if(memo[i-kazyou[j]]==-1){
 				ok=false;
 				break;
 			}
 		}
 		if(ok==true){
 			//printf("%d ",i);
 			ans+=i;
 		}
 	}
 	printf("\nans=%d %lf",ans,clock()-start);
  }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 *問い24
 順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると
 012 021 102 120 201 210
 になる.
 0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
 
 解法
 先頭桁が0になる数字列は362880通り、1も2も362880通りです。
 なので組み合わせ数で割っていけば最初の数は2であると分かります。
 2桁目以降は40320通りのどれかに分岐します。
 この時一度使った数は使えないということに注意して求めていきます。
 それだけの簡単な問題です。
 
  #include<stdio.h>
  int base[11]={0,362880,40320,5040,720,120,24,6,2,1,1};
  int main(){
 	int no=1000*1000-1;
 	bool spents[10];
 	for(int i=0;i<10;i++)spents[i]=false;
 	for(int i=1;i<11;i++){
 		int p=no/base[i]+1;
 		int count=0,j;
 		for(j=0;j<10;j++){
 			count+=!spents[j];
 			if(count>=p)break;
 		}
 		//2783915460
 		spents[j]=true;
 		printf("%d",j);
 		no=no%base[i];
 	}
  }
 
 
 
 
 *問い25
 フィボナッチ数列で1000ケタになる最初の項を求めよ。
 
 解法
 Lispで解いてもよいですし精度の高い近似式で解いてもよかったのですが簡単な近似式があったのでそちらを使いました。
 1000桁近辺はこの近似式が精度を保てるギリギリの値みたいです。
 
  #include<stdio.h>
  #include<math.h>
  int main(){
 	double b=(999+0.349)/0.209;
 	printf("%d",(int)(b+0.5));
+ }
+
+
+
+
+
+
+
+
+
+*問い26
+d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。
+
+解法
+Wikiの循環節に関する記事を参考にコードを書いてみました。
+一応正しい答えは出ますが、全ての場合で正しい答えを求めているかどうか疑問状態です。
+競技プログラムの問題なら膨大なジャッジデータでテストしてくれるのですがプロジェクトオイラーではそうでもないのが難しいところです。
+
+
+ #include<stdio.h>
+ #include<algorithm>
+ const int up=1000;
+ int memo[up+1]={0};//コードを実行すると2~999までの循環節の長さが計算されこの配列に格納される値が正しいかどうかが疑問です
+ int calc(){
+	int ansSize=0,ans=0;
+	for(int i=2;i<up;i++){
+		int ten=10,count=1;
+		if(memo[i]!=0)continue;//素数でないので計算はもうすんでいる
+		if(i%2==0||i%5==0){
+			count=-1;//2か5で割れる数は循環しないので計算量低減のためフラグとして-1を入れる
+		}else{
+			while(ten%i!=1){
+				ten=(ten*10)%i;//循環節の長さを求める
+				count++;
+			}
+		}
+		if(ansSize<count){
+			ansSize=count;//循環節の最大長が更新された
+			ans=i;//答えの数字
+		}
+		for(int j=i;j<up;j+=i){
+			memo[j]=std::max(count,memo[j]);//iの倍数jで循環節の長さを更新
+		}
+	}
+	return ans;
+ }
+ int main(){
+	printf("%d",calc());//答えの表示
  }