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

Project Euler (Problem 6,7,8,9,10)

Project Euler (Problem 6,7,8,9,10)

概要

前回、に続きプロジェクトオイラーのProblem 6,7,8,9,10 を解いた。数学力のなさがコンピューターに無駄な、無駄な、無駄な計算負荷をかけていることは重々承知の上でありますが、いかんせん書かないことには実力がつかない。数学力のなさの露呈を恐れて書かなければ、そもそも実力が向上しない。致し方ない。書くしかないではないか。Problem 10 はおもいっきりネット上の天才様の頭脳を使わせて頂きました。実力不足・・・ぐすん。。。

Problem 6

C++

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


#include <iostream>
#include <cmath>


using namespace std;


// 二乗の和を求める
int GetPowAdd(int const max)
{
 int ans = 0;
 for (int i = 1; i <= max; ++i) {
  ans += pow(i, 2);
 }

 return (ans);
}


// 和の二乗を求める
int GetAddPow(int const max)
{
 int ans = 0;
 for (int i = 1; i <= max; ++i) {
  ans += i;
 }


 ans = pow(ans, 2);
 return (ans);
}


int main(int argc, char* argv[])
{
 cout << GetAddPow(100) - GetPowAdd(100) << endl;
 return (0);
}

Perl

use strict;
use warnings;
use utf8;


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


sub getPowAdd {
 my @param = @_;
 unless (defined($param[0])) {
  die("Parameter is not set.");
 }

 my $ans = 0;
 for (my $i = 1; $i <= $param[0]; $i++) {
  # Perl のべき乗計算は 2 ** N で２のN乗となる。
  $ans += $i ** 2;
 }

 return ($ans);
}


sub getAddPow {
 my @param = @_;
 unless (defined($param[0])) {
  die("Parameter is not set.");
 }

 my $ans = 0;
 for (my $i = 1; $i <= $param[0]; $i++) {
  $ans += $i;
 }

 $ans = $ans ** 2;
 return ($ans);
}


print getAddPow(100) - getPowAdd(100);

JavaScript

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


// 二乗の和を求める
function GetPowAdd(max)
{
 var ans = 0;
 for (var i = 1; i <= max; ++i) {
  ans += Math.pow(i, 2);
 }

 return (ans);
}


// 和の二乗を求める
function GetAddPow(max)
{
 var ans = 0;
 for (var i = 1; i <= max; ++i) {
  ans += i;
 }

 ans = Math.pow(ans, 2);
 return (ans);
}


console.log(GetAddPow(100) - GetPowAdd(100));

Problem 7

C++

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


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


#include <iostream&gt
#include <vector>
#include <algorithm>


using namespace std;


vector<in> GetPrimeNumber(const vector<int>& v, int const max, int const min)
{
 vector<int> t = v;
 for (int i = min; i <= max; ++i) {
  bool flag = false;
  if (i == 1) {
   continue;
  }


  for (auto itr = t.begin(); itr != t.end(); ++itr) {
   if (*itr == 1) {
    continue;
   }

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


  if (!flag) {
   // 昔のリストに存在しない素数のみ追加する。
   t.push_back(i);
  }
 }


 return (t);
}


int main(int argc, char* argv[])
{
 int tmp = 0, ans = 0;
 vector<int> listPrimeNumber;


 listPrimeNumber.push_back(2);
 while (true) {
  if (listPrimeNumber.size() >= 10001) {
   ans = listPrimeNumber.at(10001-1);
   break;
  }


  // 素数を取得する。
  int padding = 100;
  listPrimeNumber = GetPrimeNumber(listPrimeNumber, tmp + padding, tmp);
  tmp += padding;
 }


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

Perl

use strict;
use warnings;
use utf8;


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


sub getPrimeNumber {
 my @param = @_;
 # 第一引数を実体化させてそれを配列であるとして処理する。
 my @t = @{ $param[0] };

 for (my $i = $param[2]; $i <= $param[1]; $i++) {
  my $flag = 0;
  if ($i == 1) {
   next;
  }

  # 配列の要素数を取得するときは配列を数値型として実体化させれば良い。
  # Perl は @ をつけると配列型、$ をつけると実数、整数、文字列型の変数として処理する。
  for (my $j = 0; $j < scalar(@t); $j++) {
   if ($t[$j] == 1) {
    next;
   }

   if (($i % $t[$j]) == 0) {
    # 割り切れる。素数ではない。
    $flag = 1;
    last;
   }
  }


  if (!$flag) {
   push(@t, $i);
  }
 }


 return (@t);
}


my $tmp = 0;
my $ans = 0;
my @listPN = ();
push(@listPN, 2);
while(scalar(@listPN) < 10001) {
 # 素数を取得する
 my $padding = 100;
 @listPN = getPrimeNumber(\@listPN, $tmp + $padding, $tmp);
 $tmp += $padding;
}


$ans = $listPN[10001 - 1];
print $ans;

JavaScript

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


function GetPrimeNumber(oldList, max, min)
{
 var t = oldList;
 for (var i = min; i <= max; ++i) {
  var flag = false;
  if (i == 1) {
   continue;
  }

  for (var j = 0; j < t.length; ++j) {
   if (t[j] == 1) {
    continue;
   }

   if ((i % t[j]) == 0) {
    // 割り切れる。素数ではない。
    flag = true;
    break;
   }
  }


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


 return (t);
}


var tmp = 0, ans = 0;
var listPN = [];
listPN.push(2);
while (true) {
 if (listPN.length >= 10001) {
  ans = listPN[10001 - 1];
  break;
 }


 // 素数を取得
 var padding = 100;
 listPN = GetPrimeNumber(listPN, tmp + padding, tmp);
 tmp += padding;
}


console.log(ans);

Problem 8

C++

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


#include <iostream>
#include <deque>
#include <cstring>


using namespace std;


// 一次元配列の文字列になります。
const char gNT[] = {
 "73167176531330624919225119674426574742355349194934"
 "96983520312774506326239578318016984801869478851843"
 "85861560789112949495459501737958331952853208805511"
 "12540698747158523863050715693290963295227443043557"
 "66896648950445244523161731856403098711121722383113"
 "62229893423380308135336276614282806444486645238749"
 "30358907296290491560440772390713810515859307960866"
 "70172427121883998797908792274921901699720888093776"
 "65727333001053367881220235421809751254540594752243"
 "52584907711670556013604839586446706324415722155397"
 "53697817977846174064955149290862569321978468622482"
 "83972241375657056057490261407972968652414535100474"
 "82166370484403199890008895243450658541227588666881"
 "16427171479924442928230863465674813919123162824586"
 "17866458359124566529476545682848912883142607690042"
 "24219022671055626321111109370544217506941658960408"
 "07198403850962455444362981230987879927244284909188"
 "84580156166097919133875499200524063689912560717606"
 "05886116467109405077541002256983155200055935729725"
 "71636269561882670428252483600823257530420752963450"
};


// 文字を数値に変換
inline int GetNum(char const c)
{
 return (9 - ('9' - c));
}


int main(int argc, char* argv[])
{
 deque<int> buf;
 // 問題が更新されたのでここを 13 にするといいです。
 int const countMax = 5;

 int ansN = 0;
 deque<int> ansList;


 const int tableMax = strlen(gNT);
 for (int i = 0; i < tableMax; ++i) {
  if (buf.size() > countMax) {
   // 最初の要素を削除する。
   buf.pop_front();
  }


  // 要素追加、テーブルから一文字持ってきて数値に変換。
  buf.push_back(GetNum(gNT[i]));
  if (i <= countMax) {
   continue;
  }


  // 連続する要素すべてを掛け合わせる。
  int r = buf.at(0);
  for (int j = 1; j < countMax; j++) {
   r *= buf.at(j);
  }

  if (r > ansN) {
   ansN = r;
   ansList = buf;
  }
 }


 cout << ansN << endl;
 for (auto itr = ansList.begin(); itr != ansList.end(); ++itr) {
  cout << *itr << " ";
 }
 cout << endl;
 return (0);
}

Perl

未実装

JavaScript

未実装

Problem 9

C++

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


#include <iostream>
#include <cmath>


using namespace std;


int main(int argc, char* argv[])
{
 int a = 0, b = 0, c = 0;
 bool flag = false;
 int max = 500;
 for (int i = 1; i < max; ++i) {
  if (flag) {
   break;
  }


  for (int j = 1; j < max; ++j) {
   if (flag) {
    break;
   }


   for (int k = 1; k < max; ++k) {
    if (i + j + k != 1000) {
     continue;
    }

    // ピタゴラス数として最適であるか確認
    if ((pow(i,2) + pow(j,2)) == pow(k,2)) {
     // ビンゴ。
     a = i;
     b = j;
     c = k;
     flag = true;
     break;
    }
   }
  }
 }


 cout << a << "," << b << "," << c << endl;
 cout << a+b+c << ":" << pow(a,2) << "," << pow(b,2) << "," << pow(c,2) << endl;

 cout << "Answer : " << a*b*c << endl;
 return (0);
}

Perl

未実装

JavaScript

未実装

Problem 10

C++

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


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


#include <iostream>
#include <vector>
#include <cmath>


using namespace std;


vector<__int64> GetPrimeNumber(const vector<__int64>& v, int const max, int min)
{
 vector<__int64> t = v;
 if (min < 2) {
  // 問題の仕様上 1 を素数とはしないから、最小の素数は 2 です。
  min = 2;
 }


 for (int i = min; i <= max; ++i) {
  bool flag = false;
  if (i == 1) {
   continue;
  }


  __int64 p = sqrt(i);
  for (auto itr = t.begin(); itr != t.end(); ++itr) {
   if (*itr == 1) {
    continue;
   }


   // これをつけると早くなる・・・らしい
   if (p < *itr) {
    break;
   }


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


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


 return (t);
}


int main(int argc, char* argv[])
{
 __int64 tmp = 0, ans = 0;
 vector<__int64> listPN;


 listPN = GetPrimeNumber(listPN, 2000000, 2);
 for (auto itr = listPN.begin(); itr != listPN.end(); ++itr) {
  ans += *itr;
 }

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

Perl

use strict;
use warnings;
use utf8;


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


my $ans = 0;
my @tmp = ();
for (my $i = 2; $i <= 2000000; $i++) {
 my $flag = 0;
 my $p = sqrt($i);
 foreach my $v (@tmp) {
  if ($p < $v) {
   last;
  }


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

 if ($flag == 0) {
  push(@tmp, $i);
  $ans += $i;
 }
}


print $ans;

JavaScript

未実装

感想

なんだかんだ言って一番経験のある、っていうか手に染み込んでいる C++ が一番書きやすい。Perl はまぁいろいろ言いたいことは、あるけれど、良い言語・・・だと・・・思う・・・バタリ
以上

参考

C言語でProject Euler 【Problem10】：C言語でProject Euler(プロジェクト・オイラー)に挑戦

ラベル:

このブログの人気の投稿

記述試験の書き方（仮）

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

本サイトの今後について

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

node.js で SQLite3 を使用するコードを書くときの予備録

node.js で SQLite3 を使用するコードを書くとき、予備録 まず、非同期処理。 C言語や Perl のように上から下に処理が続くと決して思ってはいけない。 SQLite3 の each は SQL 文実行完了時に呼び出す関数を指定できる SQLite をインストールします、 npm install sqlite3 [test.js] var sqlite3 = require('sqlite3').verbose(); var db = new sqlite3.Database(':memory:'); db.serialize(function() { db.run("CREATE TABLE lorem (info TEXT)"); var stmt = db.prepare("INSERT INTO lorem VALUES (?)"); for (var i = 0; i 結果 [ROW] 1: Ipsum 0 [ROW] 2: Ipsum 1 [ROW] 3: Ipsum 2 [ROW] 4: Ipsum 3 [ROW] 5: Ipsum 4 [ROW] 6: Ipsum 5 [ROW] 7: Ipsum 6 [ROW] 8: Ipsum 7 [ROW] 9: Ipsum 8 [ROW] 10: Ipsum 9 [BUF] 1: Ipsum 0 [BUF] 2: Ipsum 1 [BUF] 3: Ipsum 2 [BUF] 4: Ipsum 3 [BUF] 5: Ipsum 4 [BUF] 6: Ipsum 5 [BUF] 7: Ipsum 6 [BUF] 8: Ipsum 7 [BUF] 9: Ipsum 8 [BUF] 10: Ipsum 9 Finish. まぁ見れば分かる通り、each 関数の第三引数を指定しただけなんだけどね。 Database#each(sql, [param, ...], [callback], [complete]) https://github.com/mapbox/node-sqlite3...
続きを読む