На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> Преобразовать массив
    Есть массив {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
    Преобразовать согласно последовательности b0, bn, b1, bn+1,… , bn-1, b2n-1.
    Должно выводить 0 5 1 6 2 7 3 8 4 9

    Программа выводит 0 5 1 6 1 7 6 8 1 9

    Не могу понять что происходит с t:

    ExpandedWrap disabled
      #include "pch.h"
      #include <iostream>
       
      using namespace std;
       
      int n = 5;
      int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
      int t = a[0];
       
      int main()
      {
          for (int i = 0; i < n * 2; i++) {
              cout << a[i] << " ";
          }
          cout << endl;
          int c = n;
          for (int i = 0; i < n; i++) {
              a[i*2] = t;
              t = a[i + 1];
              a[i*2 + 1] = a[c];
              c++;
          }
          for (int i = 0; i < n*2; i++) {
              cout << a[i] << " ";
          }
      }
      Примерно так можно:
      ExpandedWrap disabled
        int n = 5, t,c, b;
            int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            t = 1, c=a[t]; // откуда и что
            for( int i=1; i<2*n-2; i++) // хвосты неподвижны
            {
            if( t<n ) // вперёд
                b = a[t*2], a[t*2] = c, t *= 2;
            else // назад
                b = a[(t-n)*2+1], a[(t-n)*2+1] = c, t = (t-n)*2+1;
            c = b;
            }
            b = a[3], a[3] = a[6], a[6] = b;
      Примечание: в данном варианте (n=5) есть особый случай a[3]<->a[6], кой обрабатывается отдельно. При n = 8 возникнет новый a[5]<->a[10]. И т.д. :yes-sad:
        Цитата Славян @
        Примерно так можно:
        ExpandedWrap disabled
          int n = 5, t,c, b;
              int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
              t = 1, c=a[t]; // откуда и что
              for( int i=1; i<2*n-2; i++) // хвосты неподвижны
              {
              if( t<n ) // вперёд
                  b = a[t*2], a[t*2] = c, t *= 2;
              else // назад
                  b = a[(t-n)*2+1], a[(t-n)*2+1] = c, t = (t-n)*2+1;
              c = b;
              }
              b = a[3], a[3] = a[6], a[6] = b;
        Примечание: в данном варианте (n=5) есть особый случай a[3]<->a[6], кой обрабатывается отдельно. При n = 8 возникнет новый a[5]<->a[10]. И т.д. :yes-sad:

        да, работает только при n=10, жаль
          Да, надо бы сделать универсальным. :oops:
            Увы, пока только так для общего случая вышло:
            ExpandedWrap disabled
                  int n = 8, t,c, b;
                  int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
                  for ( int g=1; g<2*n-2; g++)
                  {
                      t = g, c = a[t]; // откуда и что : новая орбиталь
                      for( int i=1; i<=2*n-2; i++) // хвосты неподвижны
                      {
                          t = t<n ? t*2 : (t-n)*2+1; // вперёд ИЛИ назад
                          if( a[t]<0 ) break; // здесь были, эта орбиталь обработана
                          b = a[t], a[t] = -c;
                          c = b;
                      }
                  }
                  for( int i=1; i<=2*n-2; i++) a[i] = -a[i];
              Эта задача эквивалентна транспонированию прямоугольной матрицы на месте.
              Если массив небольшой, то в общем случае лучше не извращаться, а воспользоваться промежуточным массивом.
              Или массивом индексов для перестановки.
              Перестановка без дополнительного массива тоже возможна, но там запутанный алгоритм получается. Фактически работа ведётся как с массивом индексов, только массив на лету вычисляется, и есть сложность с определением того, обработан уже элемент или нет.
                Формально это легко реализуется посредством последовательности вращений. Только неоптимально.
                  В таких задачах нужно публиковать ОГРАНИЧЕНИЯ!
                  Как правило, нужно сделать за 1-2 цикла, нельзя использовать операций сравнения и пр. пр. Всегда кол-во элементов исходного массива четно? В разных алгоритмах четность/нечетность кол-ва элементов может давать тонкости....

                  В данном случае, можно создать 2 динам.массива. Разнести в них элементы и затем слить в начальный.

                  Также, ни слова не сказано о природе входных данных! Если задана всегда возрастающая последовательность с шагом +1, начиная от 0, то можно сделать ооооооочень просто! Для заполнения текущего элемента использовать предыдущий + 1.

                  Например, так:
                  ExpandedWrap disabled
                    #include "stdafx.h"
                    #include <iostream>
                     
                    using namespace std;
                     
                     
                    int v[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
                     
                    int main()
                    {
                        int count = 10;
                        int n = count / 2;
                        for (int i = 0; i < count; i++)
                            cout << v[i] << "\t";
                        cout << endl;
                     
                        int x = v[0] - 1;
                        int y = v[n] - 1;
                        for(int i = 0; i < count; i += 2)
                        {
                            v[i] = ++x;
                            v[i + 1] = ++y;
                        }
                     
                        
                     
                        for (int i = 0; i < count; i++)
                            cout << v[i] << "\t";
                        cout << endl << endl;
                     
                        cin.get();
                        return 0;
                    }


                  возможно, нужно вывести некую алгебраическую формулу, по которой расставляются элементы! Это все нужно УКАЗЫВАТЬ в постановке задачи! Одну и ту же задачу можно выполнить лютым множеством способов...
                    Цитата FasterHarder @
                    возможно, нужно вывести некую алгебраическую формулу, по которой расставляются элементы! Это все нужно УКАЗЫВАТЬ в постановке задачи! Одну и ту же задачу можно выполнить лютым множеством способов...

                    Кстати да, возможно тут нужна именно формула (кто бы вывел?). А вот создавать новый массив нельзя, тем более динамический :D, нужно преобразовывать существующий
                    Сообщение отредактировано: Evgen121 -
                      Цитата Qraizer @
                      Формально это легко реализуется посредством последовательности вращений. Только неоптимально.
                      Есть более оптимальное решение, основанное га простом сложении в столбик. По факту у нас есть {bi}, в котором i нужно увеличить вдвое с оборотом вокруг правой границы.
                      1. Берём первый неперемещённый b и очищаем занимаемое им место.
                      2. Cдвигаем взятое b вправо на величину его индекса.
                      3. Если происходит оборот вокруг правой границы, возникает перенос, поэтому сдвигаем ещё на одну позицию.
                      4. Если назначение не очищено, берём новое b с этой позиции.
                      5. Помещаем сдвинутое b в эту позицию.
                      6. Пока у нас есть взятое b, повторяем с шага 2.
                      7. Пока у нас есть неперемещённые b, повторяем с шага 1.
                      Пример на массиве, что вверху.
                      { b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 }
                      Шаг 1. Берём неперемещённый b0.
                      { X0, b1, b2, b3, b4, b5, b6, b7, b8, b9 } ⇆ b0
                      Шаг 2. Его индекс 0, поэтому сдвигаем на 0 позиций. Шаги 3 и 4 не выполняются.
                      { b0, b1, b2, b3, b4, b5, b6, b7, b8, b9 }
                      Шаг 5. Новая позиция пуста, и у нас нет взятого b, шаг 6 не выполняется. Шаг 7. У нас есть перемещённый b1
                      Шаг 1. Берём b1.
                      { b0, X1, b2, b3, b4, b5, b6, b7, b8, b9 } ⇆ b1
                      Шаг 2. Его индекс 1, поэтому сдвигаем на 1 позицию вправо. Шаги 3 не выполняется. Шаг 4. Назначение занято, поэтому берём оттуда b2.
                      Шаг 5. Помещаем туда b1
                      { b0, X1, b1, b3, b4, b5, b6, b7, b8, b9 } ⇆ b2
                      Шаг 6. У нас есть взятое b, переходим к шагу 2.
                      Шаги 2...6 повторяются:
                      { b0, X1, b1, b3, b2, b5, b6, b7, b8, b9 } ⇆ b4
                      { b0, X1, b1, b3, b2, b5, b6, b7, b4, b9 } ⇆ b8
                      Тут шаг 3 будет выполнен, и b8, выйдя за правую границу, вызывает перенос, что сдвинет его ещё на позицию.
                      { b0, X1, b1, b3, b2, b5, b6, b8, b4, b9 } ⇆ b7
                      Далее:
                      { b0, X1, b1, b3, b2, b7, b6, b8, b4, b9 } ⇆ b5
                      { b0, b5, b1, b3, b2, b7, b6, b8, b4, b9 }
                      Последний b5 попадает в очищенное место, шаг 6 пропускается, но у нас есть неперемещённый b3, поэтому переходим в шагу 1.
                      { b0, b5, b1, X3, b2, b7, b6, b8, b4, b9 } ⇆ b3
                      { b0, b5, b1, X3, b2, b7, b3, b8, b4, b9 } ⇆ b6
                      { b0, b5, b1, b6, b2, b7, b3, b8, b4, b9 }
                      И снова есть неперемещённый b9.
                      { b0, b5, b1, b6, b2, b7, b3, b8, b4, X9 } ⇆ b9
                      { b0, b5, b1, b6, b2, b7, b3, b8, b4, b9 }
                      Он по сути остаётся на месте, и у нас нет ещё неперемещённых b, поэтому шаг 7 не выполняется, и алгоритм завершается.

                      Добавлено
                      Сложность в том, как, имея лишь один массив, помечать неперемещённые элементы и очищенные позиции. Если вопрос стоит о точно известном размере массива, можно заранее посчитать пути элементов и запрограммировать. Но если вопрос об универсальной реализации, то, видимо сначала придётся разложить размер массива на простые множители и использовать их как критерии невыполнения шага 6. И для поиска неперемещённых элементов заодно.
                      Сообщение отредактировано: Qraizer -
                        На всякий случай вот реализация с массивом признаков. Как обрабатывать массивы нечётной длины, я без понятия, поэтому сделано, как проще.
                        ExpandedWrap disabled
                          void curious_shuffle(std::vector<int>& vec)
                          {
                            std::vector<bool> moved(vec.size());
                            int  temp, cleared;
                            bool increase = vec.size() % 2 != 0;
                           
                            if (increase) vec.push_back(int());
                            for (auto i = std::find(moved.begin(), moved.end(), false) - moved.begin(); i != moved.size();
                                      i = std::find(moved.begin(), moved.end(), false) - moved.begin())
                            {
                              cleared = i;
                              temp    = vec[i];
                              do
                              {
                                i += i;
                                if (i >= vec.size())
                                  i -= vec.size()-1;
                                std::swap(temp, vec[i]);
                                moved[i] = true;
                                if (cleared == i)
                                  cleared = -1;
                              } while (cleared >= 0);
                            }
                            if (increase) vec.pop_back();
                          }
                        На Плюсах, правда, но на С перевести пара пустяков.

                        Добавлено
                        Ну и можно чуть соптимизировать, исключив из алгоритма крайние элементы, заранее выставив для них признаки в moved[]. Всё равно они всегда на своих местах остаются.

                        Добавлено
                        Всё больше убеждаюсь, что исключительно на месте если, то только вращениями. Даже разложение на простые множители потребует дополнительной памяти.

                        Добавлено
                        Вращениями – это как-то так:
                        ExpandedWrap disabled
                          void curious_shuffle(std::vector<int>& vec)
                          {
                            bool increase = vec.size() % 2 != 0;
                           
                            if (increase) vec.push_back(int());
                            auto n = vec.size() / 2;
                            auto i = vec.begin()+1;
                            while (i+n != vec.end())
                            {
                              std::rotate(i, i+n-1, i+n);
                              i+=2;
                              --n;
                            }
                            if (increase) vec.pop_back();
                          }
                        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script execution time: 0,0588 ]   [ 17 queries used ]   [ Generated: 19.03.24, 04:08 GMT ]