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

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


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

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

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

このブログの人気の投稿

node.js で SQLite を async を使用して同期的に使用する

node.js で SQLite を async を使用して同期的に使用する node.js で SQLite を使うと何が怖いって非同期処理って所。
どのようにコードが動くのか分かり辛い。

そこで同期処理っぽくしてみたい。


async というライブラリを使用するとそれっぽいことができるそうなのでサンプルを書いた。

記述試験の書き方(仮)

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