Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.223.20.57] |
|
Сообщ.
#1
,
|
|
|
Есть массив {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: #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] << " "; } } |
Сообщ.
#2
,
|
|
|
Примерно так можно:
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; |
Сообщ.
#3
,
|
|
|
Цитата Славян @ Примерно так можно: 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=10, жаль |
Сообщ.
#4
,
|
|
|
Да, надо бы сделать универсальным.
|
Сообщ.
#5
,
|
|
|
Увы, пока только так для общего случая вышло:
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]; |
Сообщ.
#6
,
|
|
|
Эта задача эквивалентна транспонированию прямоугольной матрицы на месте.
Если массив небольшой, то в общем случае лучше не извращаться, а воспользоваться промежуточным массивом. Или массивом индексов для перестановки. Перестановка без дополнительного массива тоже возможна, но там запутанный алгоритм получается. Фактически работа ведётся как с массивом индексов, только массив на лету вычисляется, и есть сложность с определением того, обработан уже элемент или нет. |
Сообщ.
#7
,
|
|
|
Формально это легко реализуется посредством последовательности вращений. Только неоптимально.
|
Сообщ.
#8
,
|
|
|
В таких задачах нужно публиковать ОГРАНИЧЕНИЯ!
Как правило, нужно сделать за 1-2 цикла, нельзя использовать операций сравнения и пр. пр. Всегда кол-во элементов исходного массива четно? В разных алгоритмах четность/нечетность кол-ва элементов может давать тонкости.... В данном случае, можно создать 2 динам.массива. Разнести в них элементы и затем слить в начальный. Также, ни слова не сказано о природе входных данных! Если задана всегда возрастающая последовательность с шагом +1, начиная от 0, то можно сделать ооооооочень просто! Для заполнения текущего элемента использовать предыдущий + 1. Например, так: #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; } возможно, нужно вывести некую алгебраическую формулу, по которой расставляются элементы! Это все нужно УКАЗЫВАТЬ в постановке задачи! Одну и ту же задачу можно выполнить лютым множеством способов... |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ возможно, нужно вывести некую алгебраическую формулу, по которой расставляются элементы! Это все нужно УКАЗЫВАТЬ в постановке задачи! Одну и ту же задачу можно выполнить лютым множеством способов... Кстати да, возможно тут нужна именно формула (кто бы вывел?). А вот создавать новый массив нельзя, тем более динамический , нужно преобразовывать существующий |
Сообщ.
#10
,
|
|
|
Цитата Qraizer @ Есть более оптимальное решение, основанное га простом сложении в столбик. По факту у нас есть {bi}, в котором i нужно увеличить вдвое с оборотом вокруг правой границы. Пример на массиве, что вверху.Формально это легко реализуется посредством последовательности вращений. Только неоптимально. { 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. И для поиска неперемещённых элементов заодно. |
Сообщ.
#11
,
|
|
|
На всякий случай вот реализация с массивом признаков. Как обрабатывать массивы нечётной длины, я без понятия, поэтому сделано, как проще.
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[]. Всё равно они всегда на своих местах остаются. Добавлено Всё больше убеждаюсь, что исключительно на месте если, то только вращениями. Даже разложение на простые множители потребует дополнительной памяти. Добавлено Вращениями – это как-то так: 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(); } |