Bisus

Untitled

Oct 30th, 2019
291
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Сдвинуть массив на k позиций влево
  2. void ShiftLeftForK(double *a, unsigned int n, unsigned int k)
  3. {
  4.     unsigned int i, j;
  5.     unsigned int start_index;
  6.     unsigned int counter = 0;// Счетчик перестановок
  7.     double buffer;
  8.  
  9.     k = k%n;
  10.     start_index = 0;// Начнем алгоритм с нулевого элемента
  11.     while(counter<n)// Пока переставлены не все элементы
  12.     {
  13.         buffer = a[start_index];
  14.  
  15.         for(i = start_index, j = (i + k)%n; j!=start_index; i = j, j = (i + k)%n)
  16.         /* Ищем элемент, который должен перейти на позицию i.
  17.          * Это элемент с индексом j = (i + k)%n.
  18.          * На следующей итерации: i = j, снова j = (i + k)%n.
  19.          * Делаем так, пока j не станет равным индексу, с которого начали.
  20.          */
  21.         {
  22.             a[i] = a[j];// Ставим элемент с индексом j на позицию i
  23.             counter++;// Перестановка сделана
  24.         }
  25.         /* j - индекс, с которого начали.
  26.          * Тогда i - индекс элемента, в который должен перейти элемент с начальным индексом.
  27.          * Элемент с начальным индексом сохранен в буфере.
  28.          */
  29.         a[i] = buffer;
  30.         counter++;// Перестановка сделана
  31.  
  32.         /* Если еще не все элементы переставлены, то на следующем витке while
  33.          * начальным элементом будет элемент с индексом на 1 больше текущего начального.
  34.          */
  35.         /* Если не все элементы переставлены, то элемент с индексом на 1 больше текущего начального не переставлялся.
  36.          * Доказательство:
  37.          *  Предположим противное.
  38.          *  Пусть виток цикла с начальным индексом previous_index переставлял элемент с индексом start_index + 1.
  39.          *  previous_index<=start_index
  40.          *  Возможны 2 случая:
  41.          *   1) previous_index<start_index
  42.          *      Тогда виток цикла с начальным индексом previous_index + 1 уже переставлял элемент с индексом start_index + 2
  43.          *      И так далее любой элемент с начальным индексом из отрезка [0,k - 1] уже был переставлен.
  44.          *      Тогда любой элемент из отрезка [0,n - 1] уже был переставлен.
  45.          *      Противоречие.
  46.          *  2) previous_index==start_index
  47.          *      Тогда каждый элемент, выбранный в качестве начального, переставляет следующий.
  48.          *      Тогда все элементы уже переставлены.
  49.          *      Противоречие.
  50.          */
  51.         start_index++;
  52.     }
  53. }
RAW Paste Data