« Project Euler - problem 014
Project Euler - problem 030 »

Project Euler - problem 015

August 1st, 2007 by Daniel Høyer Iversen

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

How many routes are there through a 20*20 grid?

I første omgang prøvde jeg å gå alle mulige veier mens jeg telte de gyldige veiene:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

 
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
 
#define grid 2
 
bool isValidRoad( int num[]);
int *startRoad();
 
int main ()
{
	clock_t start = clock();
	int res(0), pos(0);
	int* road = startRoad();
 
while(pos &gt;= 0){
	pos= 2*grid - 1;
	road[pos]++;
 
	while(road[pos]&gt;1){
		road[pos]=0;
		pos--;
		road[pos]++;
	}
 
	if(isValidRoad(road)){
		res++;
	}
 
}
 
	cout &lt;&lt; "resultatet er ";
	cout &lt;&lt; res &lt;&lt; "n";
	cout &lt;&lt; "time: "&lt;&lt; ( ( clock() - start ) / (double)CLOCKS_PER_SEC ) &lt;&lt;'n';
	return 0;
}
 
bool isValidRoad(int num[]){
int res(0);
	for(int i = 0; i &lt; 2* grid; i++){
		res += num[i];
		cout &lt;&lt; num[i];
	}
cout &lt;&lt; "n";
return (res == grid);
}
 
int *startRoad(){
	static int res[2*grid];
		for(int i = 0; i &lt; 2*grid; i++){
		res[i]=0;
	}
return res;
}
</vector></ctime></iostream>

Det fungerte veldig bra på små rutenett, men på et rutenett på 20*20 vil det ta enormt lang tid. Dermed kom jeg på at svaret egentlig er 40! / (20!)² , dermed laget jeg et nytt program som beregnet dette:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

 
#include <iostream>
#include <ctime>
using namespace std;
 
#define grid 20
 
long long choose(int num1, int num2);
 
int main ()
{
clock_t start = clock();
	long long res(1);
 
	res = 	choose( 2* grid, grid);
 
	cout &lt;&lt; "resultatet er ";
	cout &lt;&lt; res &lt;&lt; "n";
	cout&lt;&lt; ( ( clock() - start ) / (double)CLOCKS_PER_SEC ) &lt;&lt;'n';
	return 0;
}
 
long long choose(int num1, int num2){
  long long res(1);
  int temp = 1;
	for(long long i = num1; i &gt; num2; i--){
		res *= i;
		temp++;
		if( temp &lt;= num2){
			res /= temp;
		}
	}
return res;
}
</ctime></iostream>
Do you want to use this code?

1 Response to “Project Euler - problem 015”

  1. PeteX

    Or, you could just use plain mathematics, for example combinations.
    i.e. 40 C 20, which is equivalent to:
    40! / (20! * 20!) = 137846528820
    40 factorial divided by 20 factorial squared.

    Jun 30th, 2008    3:52 am   

Leave a Response

« Project Euler - problem 014
Project Euler - problem 030 »