• API
• FAQ
• Tools
• Archive
daily pastebin goal
26%
SHARE
TWEET

# Project Euler 104

wavicle Feb 13th, 2016 (edited) 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //Project Euler problem 104, 100% brute force
2. //finds the index of the first Fibonacci whose first and last nine digits are 1-9 pandigital but not necessarily in order
3.
4. #include <stdio.h>
5.
6. int main()
7. {   int fib_index=2, solutions=0;
8.
9.     int top_term[70000]={0};
10.     int bottom_term[70000]={0};
11.
12.     top_term[69999] = 1;    //fibonacci_2
13.     bottom_term[69999] = 1; //fibonacci_1
14.
15.     int marker=69998; //fib beginning marker
16.
17.     while(solutions == 0)
18.     {   for(int temp, a=69999; a >= marker; a--) //generate fibonacci (for loop)
19.         {   temp = top_term[a];
20.             top_term[a] += bottom_term[a];
21.             bottom_term[a] = temp;
22.
23.             if(top_term[a] > 9) //(if sum > 9, carry the one)
24.             {   top_term[a] %= 10;
25.                 bottom_term[a-1]++;
26.             }
27.         }
28.
29.         fib_index++;
30.         if(top_term[marker] != 0) marker--;
31.
32.         //check right fibonacci end
33.         int pan[10]={0}, approve_left=0, approve_right=0;
34.
35.         for(int temp, a=69991; a <= 69999; a++) //give pan[] right digits
36.         {   temp = top_term[a];
37.             pan[temp]++;
38.         }
39.
40.         if(pan[0] != 0) continue;
41.
42.         for(int a=1; a <= 9; a++) //check right if pandigital
43.         {   if(pan[a] == 1)
44.             {   approve_right++;
45.             }
46.         }
47.
48.         //check left fibonacci end
49.         if(approve_right != 9 || marker+1 > 69981) continue;
50.
51.         for(int a=0; a <= 9; a++) //reset pan[]
52.         {   pan[a] = 0;
53.         }
54.
55.         for(int a=marker+1, temp; a <= marker+9; a++) //give pan[] left digits
56.         {   temp = top_term[a];
57.             pan[temp]++;
58.         }
59.
60.         if(pan[0] != 0) continue;
61.
62.         for(int a=1; a <= 9; a++) //check left if pandigital
63.         {   if(pan[a] == 1)
64.             {   approve_left++;
65.             }
66.         }
67.
68.         if(approve_left == 9 && approve_right == 9)
69.         {   solutions++;
70.         }
71.     }
72.
73.     printf("fib_index: %i\n\n", fib_index);
74.
75.     return 0;
76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top