Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- void reset(int *a, int *b, int n)
- {
- int i = 0;
- for (i=0; i<n; ++i)
- {
- a[i] = i+1;
- b[i] = 1;
- }
- }
- void result(int *b, int n, char c)
- {
- int i = 0;
- for (i=0; i<n; ++i)
- printf("%c[%d]=%d ", c, i+1, b[i]);
- }
- void m1(int *a, int *b, int n)
- {
- int i = 0, j = 0;
- for (i=0; i<n; ++i)
- for (j=0; j<n; ++j)
- if (j != i)
- b[i] *= a[j];
- }
- int m2(int *a, int *b, int n)
- {
- if (n <= 1)
- {
- return a[0];
- }
- else
- {
- int i, j, k;
- j = m2(&a[n/2], &b[n/2], n-n/2);
- k = m2(a, b, n/2);
- for (i=0; i<n/2; ++i)
- b[i] *= j;
- for (i=n/2; i<n; ++i)
- b[i] *= k;
- return j*k;
- }
- }
- void m3(int *a, int *b, int n)
- {
- int i = 0;
- b[n-1] = a[n-1];
- for (i=n-2; i>=0; --i)
- b[i] = a[i]*b[i+1];
- for (i=1; i<n; ++i)
- a[i] = a[i]*a[i-1];
- for (i=0; i<n; ++i)
- b[i] = (i==0?1:a[i-1])*(i==(n-1)?1:b[i+1]);
- }
- int main(int argc, char** argv)
- {
- int n;
- if (argc<2)
- {
- printf("useage: %s <number of numbers>\n", argv[0]);
- exit(0);
- }
- else
- n = atoi(argv[1]);
- if (n <= 0)
- {
- printf("specify a number bigger than 0\n");
- exit(0);
- }
- int *a = (int*)malloc(n*sizeof(int));
- int *b = (int*)malloc(n*sizeof(int));
- reset(a, b, n);
- printf("original array: ");
- result(a, n, 'a');
- putchar('\n');
- /* method 1 */
- reset(a, b, n);
- printf("method 1 - O(n^2)\t: ");
- m1(a, b, n);
- result(b, n, 'b');
- putchar('\n');
- /* method 2 */
- reset(a, b, n);
- printf("method 2 - O(n*log(n))\t: ");
- m2(a, b, n);
- result(b, n, 'b');
- putchar('\n');
- /* method 3 */
- reset(a, b, n);
- printf("method 2 - O(n)\t\t: ");
- m3(a, b, n);
- result(b, n, 'b');
- putchar('\n');
- }
Advertisement
Add Comment
Please, Sign In to add comment