スキップしてメイン コンテンツに移動

Project Euler (Problem 1,2,3,4,5)

Project Euler (Problem 1,2,3,4,5)

概要

Project Euler  の問題をすこ～しだけ解いてみたのでその解答を残してみる。
解答の値は、「プロジェクトオイラーの解答」と一致するので正解のはずです。
ただこのコード、数学力のない文系が書いているのでいろいろよろしくないと思う。
そして数学力があればおそらく高速化、っていうか Problem 3 とかおそらく秒殺するアルゴリズムとかあるはずです。。。
今回 C++, Perl, JavaScript で解答を書いていて、書いたコードは Perl 5.8.8, node.js v0.10.25, g++ 4.6.3 で動作確認できています。
どうでもいいけど、私の開発環境って結構レガシー(node.js を除くと)な環境だな・・・バージョンを改めて確認すると・・・まぁサーバーの Perl はしっかり 5.12 にしているけどな！

Problem 1

C++

// Problem 1
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201


#include <iostream>


using namespace std;


inline bool is3or5(int const n)
{
 return ((n%3)==0 || (n%5)==0);
}


int main(int argc, char* argv[])
{
 int ans = 0;
 for (int i = 0; i < 1000; ++i) {
  ans += i*(static_cast<int>(is3or5(i)));
 }

 cout << ans << endl;
 return (0);
}

Perl

use strict;
use warnings;
use utf8;


# Problem 1
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201


# ３か５の倍数になっている数かを判定
sub is3or5 {
 my @param = @_;

 unless (defined($param[0])) {
  print "param is not set.\n";
  return (0);
 }

 # ３の倍数である数ならば、３で割ったあまりは０である。
 if (($param[0] % 3) == 0) {
#  print $param[0] . "\n";
  return (1);
 }
 elsif (($param[0] % 5) == 0) {
#  print $param[0] . "\n";
  return (1);
 }

 return (0);
}


my $ans = 0;
for (my $i = 0; $i < 1000; $i++) {
 if (is3or5($i)) {
  $ans += $i;
 }
}


print $ans . "\n";

JavaScript

// Problem 1
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201

// 3 か 5 の倍数か否かを判定
function is3or5(p) {
 if ((p % 3) == 0) {
  return (1);
 }
 else if ((p % 5) == 0) {
  return (1);
 }

 return (0);
}


var ans = 0;
for (var i = 0; i < 1000; i++) {
 if (is3or5(i)) {
  ans += i;
 }
}


console.log(ans);

Problem 2

C++

// Problem 2
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202


#include <iostream>


using namespace std;


inline bool IsEvenNumber(int const n)
{
 return ((n%2)==0);
}


int main(int argc, char* argv[])
{
 int a = 1, b = 0, c = 0;
 int ans = 0;

 while (a < 4000000) {
  c = b;
  b = a;
  a = b + c;

  ans += a * static_cast<int>(IsEvenNumber(a));
 }

 cout << ans << endl;
 return (0);
}

Perl

use strict;
use warnings;
use utf8;


# Problem 2
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202


# 渡された数が偶数であるか判定する。
sub isEvenNumber {
 if (($_[0] % 2) == 0) {
  return (1);
 }

 return (0);
}


# フィボナッチ数列を求める。
my $a = 1;
my $b = 0;
my $c = 0;

my $ans = 0;
while ($a < 4000000) {
 $c = $b;
 $b = $a;
 $a = $b + $c;

# print $a . " ";

 if (isEvenNumber($a)) {
# print "ADD : ${a}\n";
  $ans += $a;
 }
}


print "\n\n";
print "The Answer is ${ans}.\n";

JavaScript

// Problem 2
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202


// 渡された数が偶数であるか判定する。
function isEvenNumber(n) {
 if ((n % 2) == 0) {
  return (1);
 }

 return (0);
}


// フィボナッチ数列を求める。
var a = 1, b = 0, c = 0;
var ans = 0;

while (a < 4000000) {
 c = b;
 b = a;
 a = b + c;

 if (isEvenNumber(a)) {
  ans += a;
 }
}

console.log(ans);

Problem 3

C++

// Problem 3
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203


// 注意、auto 型を型推論として使用しているので、コンパイルオプションに下記を指定する必要がある。( GCC 4.6 )
// g++ problem3.cpp -std=c++0x


#include <iostream>
#include <vector>


using namespace std;


// 素数の配列を取得する。
vector<__int64> GetPrimeNumber(__int64 max)
{
 vector<__int64> tmp;
 tmp.push_back(1);
 tmp.push_back(2);

 for (__int64 i = 0; i < max; ++i) {
  bool flag = false;
  for (auto itr = tmp.begin(); itr != tmp.end(); ++itr) {
   if (*itr == 1) {
    continue;
   }

   if ((i % *itr) == 0) {
    flag = true;
    break;
   }
  }

  if (!flag) {
   tmp.push_back(i);
  }
 }

 return (tmp);
}


int main(int argc, char* argv[])
{
 vector<__int64> list;
 cout << "startup..." << endl;
 list = GetPrimeNumber(600851475143);
 cout << "check..." << endl;

 __int64 x = 600851475143;
 __int64 ans = 0;

 bool flag = true;
 while (flag) {
  flag = false;
  for (auto itr = list.begin(); itr != list.end(); ++itr) {
   if (*itr == 0 || *itr == 1) {
    continue;
   }

   if ((x % *itr) == 0) {
    flag = true;

    x /= *itr;
    if (*itr > ans) {
     ans = *itr;
    }
   }
  }
 }

 cout << ans << endl;
 return (0);
}

Perl

use strict;
use warnings;
use utf8;


# Problem 3
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203


my @listPrimeNumber = ();
sub SetupPrimeNumberList {
 my $max = $_[0];


 push (@listPrimeNumber, 1);
 push (@listPrimeNumber, 2);
 for (my $i = 0; $i < $max; $i++) {
  my $flag = 0;
  foreach my $n (@listPrimeNumber) {
   if ($n == 1) {
    # 1 はスキップ
    next;
   }


   if (($i % $n) == 0) {
    $flag = 1;
    last;
   }
  }


  if ($flag == 0) {
   push(@listPrimeNumber, $i);
  }
 }
}


print "Startup...\n";
SetupPrimeNumberList(10000);
#foreach my $n (@listPrimeNumber) {
# print $n . "\n";
#}


print "Checking...\n";
my $x = 600851475143;
my $ans = 0;
while (1) {
 my $flag = 0;
 foreach my $n (@listPrimeNumber) {
  if ($n == 0 or $n == 1) {
   next;
  }

  if (($x % $n) == 0) {
   $flag = 1;
# print $n . "\n";
   $x /= $n;
   if ($n > $ans) {
    $ans = $n;
   }
  }
 }


 # 素数になるまで切り詰めた。
 if ($flag == 0) {
  last;
 }
}


print "Answer : ${ans}\n";

JavaScript

// Problem 3
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203


function GetPrimeNumber(max)
{
 var tmp = [];
 tmp.push(1);
 tmp.push(2);

 for (var i = 0; i < max; ++i) {
  var flag = false;
  for (var j = 0; j < tmp.length; ++j) {
   if (tmp[j] == 1) {
    if (i == 1) {
     flag = true;
     break;
    }
    continue;
   }

   if ((i % tmp[j]) == 0) {
    flag = true;
    break;
   }
  }


  if (!flag) {
   tmp.push(i);
  }
 }

 return (tmp);
}


var list = [];
console.log("startup...");
list = GetPrimeNumber(600851475143);
console.log("checking...");

var x = 600851475143;
var ans = 0;

var flag = true;
while (flag) {
 flag = false;
 for (var i = 0; i < list.length; ++i) {
  if (list[i] == 0 || list[i] == 1) {
   continue;
  }

  if ((x % list[i]) == 0) {
   flag = true;

   x /= list[i];
   if (list[i] > ans) {
    ans = list[i];
   }
  }
 }
}

console.log(ans);

Problem 4

C++

// Problem 4
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204


#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;


// 3x3 は max 6 桁
bool IsLoopNumber(int const n)
{
 int len = 0;
 char buf[0xFF];


 sprintf(buf, "%d", n);
 len = strlen(buf);


/* if (buf[0] != buf[len-1]) {
  return (false);
 }

 if (len < 4) {
  // この時点で頭と尻尾の一致を確認した。
  // 2 桁 もしくは 3 桁の回文数
  // 次は n < 6, n < 8 で判定する。
  return (true);
 }*/


 // 上記を一般化
 for (int i = 0; i < len / 2; ++i) {
  if (buf[i] != buf[len-(1+i)]) {
   return (false);
  }

  if (len < (i+1)*2 + 2) {
   return (true);
  }
 }


 return (true);
}


int main(int argc, char* argv[])
{
 int ans = 0;
 for (int x = 100; x < 1000; ++x) {
  for (int y = 100; y < 1000; ++y) {
   int n = x*y;
   if (IsLoopNumber(n)) {
    // cout << n << ":" << x << "," << y << endl;

    if (n > ans) {
     ans = n;
    }
   }
  }
 }


 cout << ans << endl;
 return (0);
}

Problem 5

C++

// Problem 5
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205


#include <iostream>


using namespace std;


bool IsOk(int const n)
{
 const int max = 20;
 for (int i = 1; i <= max; ++i) {
  if ((n%i) != 0) {
   return (false);
  }
 }

 return (true);
}


int main(int argc, char* argv[])
{
 int ans = 1;
 while (true) {
  if (IsOk(ans)) {
   break;
  }
  ++ans;
 }

 cout << ans << endl;
 return (0);
}

Perl

use strict;
use warnings;
use utf8;


# Problem 5
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205


sub isOk {
 my @param = @_;

 unless (defined($param[0])) {
  die("Parameter is not set.");
 }

 my $max = 20;
 for (my $i = 1; $i <= $max; $i++) {
  if (($param[0] % $i) != 0) {
   return (0);
  }
 }

 return (1);
}


my $ans = 1;
while (1) {
 if (isOk($ans)) {
  last;
 }

 $ans++;
}


print $ans . "\n";

JavaScript

// Problem 5
// http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205


// 判定はこれで済ます。数学的美意識を持ちたくとも、私には数学的知識が不足しているのだ・・・
function IsOk(n) {
 var max = 20;
 for (var i = 1; i <= max; i++) {
  if ((n%i) != 0) {
   return (false);
  }
 }

 return (true);
}


var ans = 0;
for (var i = 1; i < 1000000000; ++i) {
 if (IsOk(i)) {
  if (i < ans || ans == 0) {
   // 最小値を取得。
   ans = i;
  }
 }
}


if (ans == 0) {
 console.log("Not found...");
}
else {
 console.log(ans);
}

感想

やはり、数学力がないとコンピューターに無駄な計算をさせてしまう。
Problem 3 の GetPrimeNumber(600851475143); これをそのままやると相当時間かかる、っていうか１日じゃ終わらないと思う。
ただ、GetPrimeNumber(10000); でも解答と同じ値は出るんだ・・・これを回答とするのは、相当グレーだとは思うが、私の実力的には仕方ない。書かないことには実力は伸びない。たとえあれなコードでも書かないことには始まらないと思いました。言い訳ですはい。
Problem 4 は回文数を数学的に処理する良い方法が思いつかなかったので、C++ で C言語的に文字列処理で解決してみたが、うーん。スマートだとは言えないよなぁっていう。Problem 4 に関してはおそらく Perl は正規表現、JavaScript でもうまくやれば行けるとは思うのだけど、ちょっと書き起こすエネルギーがわかなかったです・・・
以上
ラベル:

このブログの人気の投稿

記述試験の書き方（仮）

記述試験の書き方（仮） １，まえがき   法学部の試験では記述式の試験が出てくる。   その試験では、あるテーマについて自由に論ぜよとされている。 しかし、論ぜよと言われても、どのように論じればいいのか、すなわち、記述の仕方について教わったことがない（よくよく考えると、法的文章力を習得させる事だけが目的の授業はないと思われる）。   本稿では、私自身が法学畜になり、見聞きし、実際に活用している論述方法についてまとめている、はずである。その要点は、①条文、判例、学説を使う。②単なる事実と法的事実を区別する。③文章内に一貫性を持たせる。である。 法律と、プログラミング
続きを読む

地上権と借地権はどう違うのか についてのメモ

地上権と借地権はどう違うのか についてのメモ 設問 　地上権を設定した土地上に建物を建築する場合と借地権者（土地に対する賃貸借契約）が土地上に建物を建築する場合はどう違うのか。 民法は人にも物にも適用される
続きを読む

本サイトの今後について

告知 本サイトは今後更新されることは、おそらくありません。 過去記事等はこのまま放置するつもりです。内容の陳腐化並びにその正確性等については保証はできません。自己責任で活用いただければと思います。 This site won't update in future. And Thank's everyone. new site -> sysrigar
続きを読む