Bisus

Untitled

Oct 24th, 2019
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void Invert(double *a, unsigned int n);
  4. void ShiftLeft(double *a, unsigned int n);
  5. int RemoveNegative(double *a, unsigned int n);
  6. void ShiftLeftForK(double *a, unsigned int n, unsigned int k);
  7. void printf_array(double *a, unsigned int n);
  8.  
  9. void printf_array(double *a, unsigned int n)
  10. {
  11.     unsigned int i;
  12.  
  13.     for(i = 0; i<n; i++)
  14.         printf("a[%u]=%lf\t", i, a[i]);
  15.  
  16.     printf("\n");
  17. }
  18.  
  19. // Сдвинуть массив на k позиций влево
  20. void ShiftLeftForK(double *a, unsigned int n, unsigned int k)
  21. {
  22.     unsigned int i, j;
  23.     unsigned int start_index;
  24.     unsigned int counter = 0;// Счетчик перестановок
  25.     double buffer;
  26.  
  27.     k = k%n;
  28.     start_index = 0;// Начнем алгоритм с нулевого элемента
  29.     while(counter<n)// Пока переставлены не все элементы
  30.     {
  31.         buffer = a[start_index];
  32.  
  33.         for(i = start_index, j = (i + k)%n; j!=start_index; i = j, j = (i + k)%n)
  34.         /* Ищем элемент, который должен перейти на позицию i.
  35.          * Это элемент с индексом j = (i + k)%n.
  36.          * На следующей итерации: i = j, снова j = (i + k)%n.
  37.          * Делаем так, пока j не станет равным индексу, с которого начали.
  38.          */
  39.         {
  40.             a[i] = a[j];// Ставим элемент с индексом j на позицию i
  41.             counter++;// Перестановка сделана
  42.         }
  43.         /* j - индекс, с которого начали.
  44.          * Тогда i - индекс элемента, в который должен перейти элемент с начальным индексом.
  45.          * Элемент с начальным индексом сохранен в буфере.
  46.          */
  47.         a[i] = buffer;
  48.         counter++;// Перестановка сделана
  49.  
  50.         /* Если еще не все элементы переставлены, то на следующем витке while
  51.          * начальным элементом будет элемент с индексом на 1 больше текущего начального.
  52.          */
  53.         /* Если не все элементы переставлены, то элемент с индексом на 1 больше текущего начального не переставлялся.
  54.          * Доказательство:
  55.          *  Предположим противное.
  56.          *  Пусть виток цикла с начальным индексом previous_index переставлял элемент с индексом start_index + 1.
  57.          *  previous_index<=start_index
  58.          *  Возможны 2 случая:
  59.          *   1) previous_index<start_index
  60.          *      Тогда виток цикла с начальным индексом previous_index + 1 уже переставлял элемент с индексом start_index + 2
  61.          *      И так далее любой элемент с начальным индексом из отрезка [0,k - 1] уже был переставлен.
  62.          *      Тогда любой элемент из отрезка [0,n - 1] уже был переставлен.
  63.          *      Противоречие.
  64.          *  2) previous_index==start_index
  65.          *      Тогда каждый элемент, выбранный в качестве начального, переставляет следующий.
  66.          *      Тогда все элементы уже переставлены.
  67.          *      Противоречие.
  68.          */
  69.         start_index++;
  70.     }
  71. }
  72.  
  73. // Все не отрицательные группируются в начале, возвращается их количество
  74. int RemoveNegative(double *a, unsigned int n)
  75. {
  76.     unsigned int i, j;
  77.  
  78.     i = 0;
  79.     for(j = 0; j<n; j++)
  80.     {
  81.         if(a[j]>=0)
  82.         {
  83.             a[i] = a[j];
  84.             i++;
  85.         }
  86.     }
  87.  
  88.     return (i - 1);
  89. }
  90.  
  91. // Расположить элементы массива в обратном порядке
  92. /* Пример использования:
  93.  * Invert(a,n);
  94.  * Invert(a, n - k);
  95.  * Invert(a + n - k, k);
  96.  * Здесь реализована перестановка подмассива, стоящего в начала, и его дополнения.
  97.  * */
  98. void Invert(double *a, unsigned int n)
  99. {
  100.     double c;
  101.     unsigned int i;
  102.  
  103.     if(n<2) return;
  104.  
  105.     for(i = 0; i<n/2; i++)
  106.     {
  107.         c = a[i];
  108.         a[i] = a[n - i - 1];
  109.         a[n - i - 1] = c;
  110.     }
  111. }
  112.  
  113. // Циклический сдвиг
  114. void ShiftLeft(double *a, unsigned int n)
  115. {
  116.     double c;
  117.     unsigned int i;
  118.  
  119.     if(n<2) return;
  120.  
  121.     c = a[0];
  122.     for(i = 1; i<n; i++)
  123.     {
  124.         a[i-1] = a[i];
  125.     }
  126.     a[n-1] = c;
  127. }
  128.  
  129. int main(void)
  130. {
  131.     FILE *input_file;
  132.     double *a;
  133.     unsigned int i,n,k;
  134.  
  135.     if((input_file = fopen("input", "r"))==NULL)
  136.     {
  137.         printf("Open file error!\n");
  138.         return 1;
  139.     }
  140.  
  141.     if(fscanf(input_file, "%d", &n)<=0)// Первое считываемое число - кол-во элементов в массиве
  142.     {
  143.         printf("Input from file error!\n");
  144.         return 2;
  145.     }
  146.  
  147.     if(n==0)
  148.     {
  149.         printf("Result: no elements!\n");
  150.         return 0;
  151.     }
  152.     a = (double *)malloc(n*sizeof(double));
  153.     for(i = 0; i<n; i++)
  154.     {
  155.         if(fscanf(input_file, "%lf", &a[i])<=0)
  156.         {
  157.             printf("Input from file error!\n");
  158.             free(a);
  159.             return 2;
  160.         }
  161.     }
  162.  
  163.     printf_array(a,n);
  164.     printf("k=");
  165.     scanf("%u", &k);
  166.     ShiftLeftForK(a,n,k);
  167.     printf("Result: ");
  168.     printf_array(a,n);
  169.  
  170.     return 0;
  171. }
RAW Paste Data