vistb

tencent-question-one

Apr 12th, 2012
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.80 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. void reset(int *a, int *b, int n)
  6. {
  7.   int i = 0;
  8.  
  9.   for (i=0; i<n; ++i)
  10.   {
  11.     a[i] = i+1;
  12.     b[i] = 1;
  13.   }
  14. }
  15.  
  16. void result(int *b, int n, char c)
  17. {
  18.   int i = 0;
  19.   for (i=0; i<n; ++i)
  20.     printf("%c[%d]=%d ", c, i+1, b[i]);
  21. }
  22.  
  23. void m1(int *a, int *b, int n)
  24. {
  25.   int i = 0, j = 0;
  26.  
  27.   for (i=0; i<n; ++i)
  28.     for (j=0; j<n; ++j)
  29.       if (j != i)
  30.         b[i] *= a[j];
  31. }
  32.  
  33. int m2(int *a, int *b, int n)
  34. {
  35.   if (n <= 1)
  36.   {
  37.     return a[0];
  38.   }
  39.   else
  40.   {
  41.     int i, j, k;
  42.     j = m2(&a[n/2], &b[n/2], n-n/2);
  43.     k = m2(a, b, n/2);
  44.     for (i=0; i<n/2; ++i)
  45.       b[i] *= j;
  46.     for (i=n/2; i<n; ++i)
  47.       b[i] *= k;
  48.     return j*k;
  49.   }
  50. }
  51.  
  52. void m3(int *a, int *b, int n)
  53. {
  54.   int i = 0;
  55.  
  56.   b[n-1] = a[n-1];
  57.   for (i=n-2; i>=0; --i)
  58.     b[i] = a[i]*b[i+1];
  59.   for (i=1; i<n; ++i)
  60.     a[i] = a[i]*a[i-1];
  61.   for (i=0; i<n; ++i)
  62.     b[i] = (i==0?1:a[i-1])*(i==(n-1)?1:b[i+1]);
  63. }
  64.  
  65. int main(int argc, char** argv)
  66. {
  67.   int n;
  68.  
  69.   if (argc<2)
  70.   {
  71.     printf("useage: %s <number of numbers>\n", argv[0]);
  72.     exit(0);
  73.   }
  74.   else
  75.     n = atoi(argv[1]);
  76.  
  77.   if (n <= 0)
  78.   {
  79.     printf("specify a number bigger than 0\n");
  80.     exit(0);
  81.   }
  82.  
  83.   int *a = (int*)malloc(n*sizeof(int));
  84.   int *b = (int*)malloc(n*sizeof(int));
  85.  
  86.   reset(a, b, n);
  87.   printf("original array: ");
  88.   result(a, n, 'a');
  89.   putchar('\n');
  90.  
  91.   /* method 1 */
  92.   reset(a, b, n);
  93.   printf("method 1 - O(n^2)\t: ");
  94.   m1(a, b, n);
  95.   result(b, n, 'b');
  96.   putchar('\n');
  97.  
  98.   /* method 2 */
  99.   reset(a, b, n);
  100.   printf("method 2 - O(n*log(n))\t: ");
  101.   m2(a, b, n);
  102.   result(b, n, 'b');
  103.   putchar('\n');
  104.  
  105.   /* method 3 */
  106.   reset(a, b, n);
  107.   printf("method 2 - O(n)\t\t: ");
  108.   m3(a, b, n);
  109.   result(b, n, 'b');
  110.   putchar('\n');
  111. }
Advertisement
Add Comment
Please, Sign In to add comment