Project Euler

Project Euler Problem 15

steloflute 2012. 5. 29. 23:02


Problem 15

19 April 2002

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?


Answer:
137846528820

 

 

n right moves

n down moves

choose n down moves out of 2n, where n = 20

40C20


C#
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    class Program {
        static void Main(string[] args) {            
            // 40! / 20! / 20!
            // = 40(39)..21 / 20!
            BigInteger p = 1;
            for (int i = 40; i >= 21; i--) {
                p *= i;
            }
            for (int i = 20; i >= 1; i--) {
                p /= i;
            }
            Console.WriteLine(p);
            Console.ReadKey();
        }
    }
}

Python


def problem15(): # 40! / 20! / 20! # = 40(39)..21 / 20! p = 1 for i in xrange(40, 20, -1): p *= i for i in xrange(20, 0, -1): p /= i print p problem15()



Go


func problem15() { // 40! / 20! / 20! // = 40(39)..21 / 20! p := big.NewInt(1) for i := 40; i >= 21; i-- { p.Mul(p, big.NewInt(int64(i))) } for i := 20; i >= 1; i-- { p.Div(p, big.NewInt(int64(i))) } fmt.Println(p) } func main() { problem15() }



C++


#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std;


class BigInteger { private: string value; public: BigInteger() : value("0") {} BigInteger(string s): value(s) {} BigInteger operator +(BigInteger other) { auto length = max(value.length(), other.value.length()); string r = ""; auto carry = 0; for (unsigned int d = 0; d <= length - 1; d++) { auto s = carry + (*this)[d] + other[d]; auto s2 = s % 10; r = ::ToString(s2) + r; carry = s / 10; } if (carry > 0) r = ::ToString(carry) + r; return BigInteger(r); } BigInteger operator *(int other) { auto length = value.length(); string r = ""; auto carry = 0; for (unsigned int d = 0; d <= length - 1; d++) { auto s = carry + (*this)[d] * other; auto s2 = s % 10; r = ::ToString(s2) + r; carry = s / 10; } if (carry > 0) r = ::ToString(carry) + r; return BigInteger(r); } BigInteger operator /(int other) { BigInteger r = ""; int carry = 0; for (unsigned int i = 0; i < value.length(); i++) { int c = value[i] - '0'; int c2 = c + carry * 10; carry = c2 % other; c2 /= other; if (r.value.length() > 0 || c2 != 0) r.value += ::ToString(c2); } return r; } int operator [](unsigned int digit) { auto length = value.length(); if (digit > length - 1) return 0; return value[length - 1 - digit] - '0'; } string ToString() { return value; } }; void problem15() { // 40! / 20! / 20! // = 40(39)..21 / 20! BigInteger p = "1"; for (int i = 40; i >= 21; i--) { p = p * i; } for (int i = 20; i >= 1; i--) { p = p / i; } cout << p.ToString() << endl; }


 

Racket

 

(define (problem15)
  ; 40! / 20! / 20!
  (display (/ (apply * (range 40 20 -1)) (apply * (range 20 0 -1)))))


 

'Project Euler' 카테고리의 다른 글

Project Euler Problem 60  (0) 2012.06.03
Project Euler Problem 59  (0) 2012.05.29
Project Euler Problem 14  (0) 2012.05.29
Project Euler Problem 13  (0) 2012.05.29
Project Euler Problem 12  (0) 2012.05.29