Комментарии 38
которые имеют закономерность в порядке следования.
До:
массив int x[] = { 1 2 3 4 5 6 7 8 }
закономерность x[n+1] = 2*x[n]-x[n-1];
После например:
x[] = {8 7 6 5 4 3 2 1 }
закономерность x[n+1] = 2*x[n]-x[n-1];
Ну надо же :)
Выражайтесь корректнее пожалуйста.
Например: для n-1 выпало n-2, для n-2 выпало n-3 и так далее для 1 выпал очевидно 0
получите подстановку (n-1,0,1,2,3,..,n-3,n-2), что противоречит условию задачи.
Вам нужна функция без неподвижной точки, обладающая некоторым свойством «перемешивания». Если n «мало» то можно подогнать. Зафиксируйте генератор псевдослучайных чисел и его начальное состояние.
1 структура данных «список» ( смотрите википедию ) в общем случае не имеет быстрого доступа по индексу ( спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован ) та структура данных что Автор имеет в виду называется «массив» у которого гарантирован доступ к элементу по индексу О(1)
2 На самом деле это очень забавная задача, у которой корректная формулировка условия намного более нетривиальна чем ее решение — к примеру Автор однозначно не справился с формулировкой условия задачи. В определенном смысле приведённое автором решение и является минимальным описанием задачи, поэтому для олимпиады она ну никак не подходит.
3 На практике- именно таким образом все программисты массивы и перемешивают, если хотят хорошо помешать карты например.
Вообщем алгоритм +( ну он очень школьный ), а статья -
спасибо Microsoft за путаницу с IList в котором доступ по индексу в О(1) в документации не упомянут, хотя скорее всего реализован
скорее всего реализован?
IList — это интерфейс. Он не содержит реализации, поэтому в документации ничего не сказано про это. Так что не надо Microsoft зря ругать :)
Если мы хотим гарантий — надо использовать конкретную структуру данных.
Если хотим универсальности — через интерфейс.
Автор выбрал второй путь.
Хорошая задачка, приходилось её решать. Приведённое решение неплохо справляется с задачей, но всё становится хитрее, если элементы повторяются, как например, буквы в реальном тексте. В таком, более общем виде, эта задача хорошо разобрана на Rosetta code. Там приводится и моё решение для Haskell, решающее задачу с фиксированным объёмом используемой памяти и за линейное время (в on-line режиме).
Shuffle the characters of a string in such a way that as many of the character values are in a different position as possible.задача сформулирована интуитивно понятно, однако некорректно
Там есть элементарная метрика, которую можно минимизировать. Но, вы правы, для более точной постановки задачи следовало бы использовать какую-либо дистанцию между строками. Но в таком случае решение задачки потребует строгого доказательства, тестирования будет недостаточно.
Напомнило: однажды собеседовался в один проект СколТеха и мне дали задачу "реалезуйте цепь Маркова второго рода, скормите ей текст и сгенерируйте новый с ее помощью, покройте все тестами и красивыми интерфейсами".
Сам удивился, но сделал.
После стал расспрашивать о том, что же за космические задачи надо решать, коль такие вещи сходу спрашиваете? Оказалось, что все то же "сторонние api интегрировать".
Но все очень серьезно...
list<T>::iterator I1 = list.begin();
list<T>::iterator I2 = list.begin();
I2++;
list<T>::iterator Istop = list.end();
while(I2 < Istop)
{
list.swap(I1, I2);
I1++; I1++;
I2++; I2++;
}
// Если количество элементов нечётное, меняем последний с первым
if(I1 < Istop)
{
list<T>::iterator I2 = list.begin();
list.swap(I1, I2);
}
в результате ни один элемент не останется на прежнем месте, да и закономерность будет нарушена. То что закономерность сохранится через 1 элемент — не противоречит условию задачи, там не сказано насколько должна быть нарушена закономерность. А может просто «развернуть» список концом вперёд и тогда закономерность снова не останется прежней, более того, она инвертируется? Задача недоформулирована, как будто подразумевается что речь пойдёт о перемешивании методом Монте-Карло, и студент выберет это решение как само собой разумеющееся. Для олимпиадной задачи эта очень куцая.
4a есть в продаже
Может, лучше Кормена?
Пусть p>1 и (p,n) =1.
i'=i*p mod n.
Как-то так. Есть более извращенные идеи на этой основе, но думаю в данном случае это не нужно.
Необходимо перемешать элементы списка, чтобы ни один элемент списка не стоял на прежнем месте, а также чтобы закономерность в порядке следования нарушилась, то есть просто циклически сдвинуть элементы вправо или влево недостаточно.
Мне вот тоже не понятно это требование. Предположим, что циклический сдвиг недостаточен. Но предложенное решение, будучи вероятностным, способно дать в результате циклический сдвиг — значит, оно некорректно.
При этом, скажем, есть тривиальное решение (для последовательности из более чем 3 элементов, все элементы уникальны), при котором последовательность просто разворачивается из конца в начало (если число элементов нечетное, средний элемент сначала обменивается с первым). Ни один из элементов не остается на своем месте, закономерность нарушена, вычислительная сложность O(n). Что я делают не так?
int maxIndex = list.Count - 1; for (int i = 0; i < maxIndex; i++) { int rightIndex = maxIndex - i;
А зачем так сложно, почему нельзя сразу написать for (var rightIndex = list.Count-1; rightIndex >= 1; rightIndex--)?
Собственно, я зашёл сюда поинтересоваться: какая компания является лучшей в мире? И по каким критериям. Спасибо.
И второй вопрос — что это за самая лучшая компания в мире?)
— придется завести битовую карту размером до 12Кб;
— степень перемешивания будет похуже, хотя, формально, исходная закономерность нарушится и никто не останется на том же месте.
Олимпиадные задачи в промышленном программировании. Часть 1