プロジェクトオイラー問い21～30 の編集履歴一覧 - c21coterie @ ウィキ

プロジェクトオイラー問い21～30 - (2012/12/14 (金) 20:15:04) の編集履歴(バックアップ)

問い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～ｎまでの約数を求める計算は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 というスコアを持つ.
ファイル中の全名前のスコアの合計を求めよ.

解法
この問題回答者が二つのグループに分かれる気がします。
テキスト処理が得意なスクリプト言語の性能を最大限に引き出し数行のコードで問題を解く人と普通に３０行程度使って解く人です。
私は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

ある数ｍはｍの倍数になる数は全てｍを約数に持ちます、つまりｍの倍数の約数の和にはすべてｍを足しておくといいわけです。
これを利用してsetKazyousuu関数のなかで約数の和をmemoに入れていきます。
計算を高速化するために過剰数になった数だけmemo[i]=-1と入れておきます。
後はmainループの中で過剰数を調べればコード実行時間０．０１６秒となります。

#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);
}

c21coterie @ ウィキ