|
1 /** |
|
2 * $Id: main.c,v 1.1.1.1 2008-04-28 17:32:53 mbroeker Exp $ |
|
3 * $Author: mbroeker $ |
|
4 * |
|
5 * lotto.c |
|
6 * computes the best n lottery-values from m loops out of [1..end] |
|
7 * |
|
8 * ------------------------------------------------------------------------------ |
|
9 * | ==18509== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 13 from 1) | |
|
10 * | ==18509== malloc/free: in use at exit: 0 bytes in 0 blocks. | |
|
11 * | ==18509== malloc/free: 10,003 allocs, 10,003 frees, 280,600 bytes allocated. | |
|
12 * ------------------------------------------------------------------------------ |
|
13 * |
|
14 */ |
|
15 |
|
16 #include <stdio.h> |
|
17 #include <stdlib.h> |
|
18 #include <getopt.h> |
|
19 #include <time.h> |
|
20 |
|
21 #ifndef DEBUG |
|
22 #warning "NO DEBUG SUPPORT: COMPILE with -DDEBUG" |
|
23 #endif |
|
24 |
|
25 #define ONESECOND 500000 |
|
26 |
|
27 typedef long int LONG; |
|
28 |
|
29 /* |
|
30 * compare function for qsort |
|
31 */ |
|
32 |
|
33 LONG compare (LONG * a, LONG * b) |
|
34 { |
|
35 if (*a > *b) |
|
36 return 1; |
|
37 else |
|
38 return -1; |
|
39 } |
|
40 |
|
41 /* |
|
42 * lottery number generator for num values [ 1..end ] |
|
43 */ |
|
44 |
|
45 LONG *lottery (LONG end, LONG num) |
|
46 { |
|
47 int i, j; |
|
48 LONG *z; |
|
49 int unique; |
|
50 |
|
51 if ((z = (LONG *) calloc (num + 1, sizeof (int))) == NULL) |
|
52 exit (0); |
|
53 |
|
54 for (i = 0; i < num; i++) { |
|
55 do { |
|
56 z[i] = 1 + (int)((float)end * rand () / (RAND_MAX + 1.0)); |
|
57 unique = 1; |
|
58 for (j = 0; j < i; j++) { |
|
59 if (z[j] == z[i]) { |
|
60 unique = 0; |
|
61 break; |
|
62 } |
|
63 } |
|
64 } while (!unique); |
|
65 } |
|
66 |
|
67 qsort (z, num, sizeof (int), (void *)&compare); |
|
68 |
|
69 return z; |
|
70 } |
|
71 |
|
72 /* |
|
73 * evaluates an array of numbers with num elements |
|
74 */ |
|
75 |
|
76 LONG *evaluation (LONG * numbers, int num, int verbose) |
|
77 { |
|
78 int i, j, k; |
|
79 int printed; |
|
80 LONG *values; |
|
81 LONG *z; |
|
82 |
|
83 int found; |
|
84 |
|
85 if (verbose) { |
|
86 printf ("\nProbabilistic evaluation\n------------------------\n"); |
|
87 for (i = 0; i < num; i++) |
|
88 printf ("%4d: %8ld times\n", i + 1, numbers[i]); |
|
89 printf ("\n"); |
|
90 } |
|
91 |
|
92 if ((values = calloc (num + 1, sizeof (int))) == NULL) |
|
93 exit (0); |
|
94 |
|
95 if ((z = calloc (num + 1, sizeof (int))) == NULL) |
|
96 exit (0); |
|
97 |
|
98 for (j = 0; j < num; j++) { |
|
99 values[j] = numbers[j]; |
|
100 } |
|
101 |
|
102 qsort (numbers, num, sizeof (int), (void *)&compare); |
|
103 |
|
104 /* |
|
105 * numbers = sorted list |
|
106 * values = unsorted list |
|
107 */ |
|
108 |
|
109 printed = k = 0; |
|
110 |
|
111 #ifdef DEBUG |
|
112 printf ("The following algorithm seems to be too slow\n"); |
|
113 #endif |
|
114 |
|
115 /* |
|
116 * REPLACE THIS |
|
117 */ |
|
118 |
|
119 for (i = 0; i < num; i++) |
|
120 for (j = 0; j < num; j++) { |
|
121 if (numbers[i] == values[j]) { |
|
122 found = 0; |
|
123 for (k = 0; k < printed; k++) |
|
124 if (z[k] == j) { |
|
125 found = 1; |
|
126 break; |
|
127 } |
|
128 |
|
129 if (!found) |
|
130 z[printed++] = j; |
|
131 } |
|
132 } |
|
133 |
|
134 #ifdef DEBUG |
|
135 printf ("The algorithm ran %d times\n", i * j * k); |
|
136 #endif |
|
137 |
|
138 /* |
|
139 * SLOW PIECE OF CODE |
|
140 */ |
|
141 |
|
142 free (values); |
|
143 |
|
144 return z; |
|
145 }; |
|
146 |
|
147 int main (int argc, char **argv) |
|
148 { |
|
149 LONG *values; |
|
150 LONG *numbers; |
|
151 LONG max; |
|
152 |
|
153 int i, j; |
|
154 |
|
155 int found; |
|
156 int loop; |
|
157 |
|
158 int verbose, wide, end, num; |
|
159 |
|
160 verbose = wide = 0; |
|
161 end = 49; |
|
162 num = 6; |
|
163 max = ONESECOND; |
|
164 |
|
165 while ((i = getopt (argc, argv, "m:e:n:vwh")) >= 0) { |
|
166 switch (i) { |
|
167 case 'm': |
|
168 max = atol (optarg); |
|
169 break; |
|
170 case 'e': |
|
171 end = atoi (optarg); |
|
172 break; |
|
173 case 'n': |
|
174 num = atoi (optarg); |
|
175 break; |
|
176 case 'v': |
|
177 verbose = 1; |
|
178 break; |
|
179 case 'w': |
|
180 verbose = 1; |
|
181 wide = 1; |
|
182 break; |
|
183 case 'h': |
|
184 printf ("Usage: %s [ -e end | -m max | -n num | -v | -w ]\n", argv[0]); |
|
185 printf (" -e: Numbers from [1..end]\n"); |
|
186 printf (" -m: evaluates max loops\n"); |
|
187 printf (" -n: n-numbers from [1..end]\n"); |
|
188 printf (" -v: verbose output\n"); |
|
189 printf (" -w: verbose and wide output\n"); |
|
190 return 0; |
|
191 } |
|
192 } |
|
193 |
|
194 if (num >= end) |
|
195 num = end - 1; |
|
196 |
|
197 srand (time (NULL)); |
|
198 |
|
199 if ((numbers = calloc (end + 1, sizeof (int))) == NULL) |
|
200 exit (0); |
|
201 |
|
202 for (loop = 0; loop < end; loop++) |
|
203 numbers[loop] = 0; |
|
204 |
|
205 for (loop = 0; loop < max; loop++) { |
|
206 values = lottery (end, num); |
|
207 for (i = 0; i < end; i++) { |
|
208 found = 0; |
|
209 for (j = 0; j < num; j++) |
|
210 if (values[j] == i + 1) { |
|
211 if (verbose) |
|
212 printf ("%3s", "XX"); |
|
213 |
|
214 numbers[i]++; |
|
215 found = 1; |
|
216 break; |
|
217 } |
|
218 |
|
219 if (verbose) { |
|
220 if (!found) |
|
221 printf ("%3d", i + 1); |
|
222 } |
|
223 |
|
224 if (wide) { |
|
225 if ((i % 7) == 0) |
|
226 printf ("\n"); |
|
227 } |
|
228 } |
|
229 |
|
230 if (verbose) |
|
231 printf ("\n"); |
|
232 |
|
233 free (values); |
|
234 } |
|
235 |
|
236 values = evaluation (numbers, end, verbose); |
|
237 |
|
238 for (i = 0; i < num; i++) |
|
239 numbers[i] = values[(end - 1) - i]; |
|
240 |
|
241 qsort (numbers, num, sizeof (int), (void *)&compare); |
|
242 |
|
243 for (i = 0; i < num; i++) |
|
244 printf ("%ld ", numbers[i] + 1); |
|
245 |
|
246 printf ("\n"); |
|
247 |
|
248 free (values); |
|
249 free (numbers); |
|
250 |
|
251 return 0; |
|
252 } |