プロジェクトオイラー問い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);
}

問い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になる数字列は３６２８８０通り、1も２も３６２８８０通りです。
なので組み合わせ数で割っていけば最初の数は２であると分かります。
２桁目以降は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];
}
}

c21coterie @ ウィキ