Problem 8 「数字列中の最大の積」 †

以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか.
データが多いので問題の詳細はリンク先を読んでください。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%208


解法

おそらくファイル読み込みの演習だと思います。
文字列やファイル読み込みは言語によって雑多な違いがあり統一的な話はできません。
まず1000文字の数字列をテキストファイルに保存し、このファイルの中身を文字列型に読み込んでいきます。


まず1000文字の数字を文字列として一行ずつ読み込み、
読み込んだ行strとしてstrAll+=strのように読み込み1000文字の文字列とします。

文字列型オブジェクトがない言語では配列やリストとして文字列を保存します。

配列の場合、一文字ずつ配列に読み込み、改行を読み込んだ場合配列に入れないで捨てて次の文字を読み込みファイル終端まで読み込みます。
リストの場合も同様です。
int p=0;
strAll[1001];
while(ファイル終端でないならば){
   char c=read();ファイルから一文字読み込む
   if(c==改行コード)ならばcontinue;
   strAll[p]=c;
   p++;
}
のようなイメージで読み込みます。
言語によって違うので各自自分の言語で確認してください。

文字列をファイルから読み込んだ後は
i=0~996まで回して。
t=(strAll[i]-'0')*(strAll[i+1]-'0')*(strAll[i+2]-'0')*(strAll[i+3]-'0')*(strAll[i+4]-'0')
と計算します。
この式はi文字目からi+4文字目までの5桁の数字の掛け算を求めています。

ans=0;
for(int i=0;i<=996;i++){
     t=(strAll[i]-'0')*(strAll[i+1]-'0')*(strAll[i+2]-'0')*(strAll[i+3]-'0')*(strAll[i+4]-'0')
     if(t>ans)ans=t;
}
こんな感じで答えが求まります。

なぜこれで計算ができるかというと文字列の正体が文字コードの列という数字の配列が正体となります。
たとえばstr="012abc"という文字列があればこの文字列の正体は数字の配列です。
(48,49,50,97,98,99)という数字の配列が文字列の正体となります。
str[2]=50
str[3]=97
という風に文字列の文字コードにアクセスできます。

数字の0~9は48~57番までの文字コードが割り当てられていてこれは世界共通です。
一文字ずつ
0=48
1=49
2=50
,,,
9=57
という具合です。

たとえば文字3を数字に変化するには'3'-'0'とすれば'3'-'0'=3と数字に変換できます。
strの例でいえば
str[2]-'0'=3と3を取り出せます。

str[5]="3241"なら
str[0]-'0'で3
str[1]-'0'で2
str[2]-'0'で4
str[3]-'0'で1


という具合に取り出せます。

文字コードは2バイト文字や3バイト文字、aAbBcCと並ぶ文字コードやabc,,,yzABCと並ぶ文字コードがあり奥が深い話です。
プロジェクトオイラーではアスキーコードという文字コードだけしっていればよいので深く考えなくても解けます。
アスキーコードの資料。
http://www9.plala.or.jp/sgwr-t/c_sub/ascii.html

必要はありませんが文字コード専門のハッカーがいるほど奥が深い世界ですので詳しい解説は色々なサイトを見て調べてください。

ちょいテクとして
改行を削除してコード中にそのまま1000文字の文字列としていれておくと楽でいいでしょう。
nums="73167,,,963450"
とか
nums[1001]="73167,,,963450"
という感じで言語によって違いますがこれは楽な手法です。

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年01月09日 16:22