Пятничные задачки. Вася Пупкин еще жив ;)

← →
MBo © (2007-11-16 09:00) [0]

1. Васе Пупкину поручили организовать сообщение с резидентом разведки в некой
стране. У Васи имеется микросейф с двумя замками A и B и два ключа от замка A.
У резидента есть два ключа от замка B. Сейф с документами будет пересылаться
обычной почтой. Как застраховаться от утечки информации при пересылке сейфа туда-сюда?

2. Вася Пупкин в полдень посадил на секундную стрелку часов муху и стал за ней
наблюдать, причем он заметил, что поведение мухи таково:
Если муха обгоняет какую-то стрелку, или ее обгоняет какая-то стрелка
(кроме секундной, у часов есть часовая и минутная стрелки),
то муха переползает на эту стрелку.
Чтобы это занятие не было пустым времяпрепровождением,
он почти по совету Козьмы Пруткова стал считать, сколько она проедет кругов.
Так сколько кругов проедет муха в течение часа?

3. Опять про муху ;)
Летела муха со скоростью метр в секунду.
И вдруг начала ускоряться по такому принципу:
каждый раз, пролетая еще один метр, она удваивала скорость.
Оцените время облета вокруг земного шара по экватору,
считая с того самого момента, когда Муха начала ускоряться.
З.Ы. пусть скорость света равна бесконечности

4. Вася Пупкин лег спать между 23 и 24 часами, а встал между 8 и 9 часами.
Сколько времени (точно) он проспал, если минутная и часовая стрелки в
момент начала и конца сна поменялись местами?

5. а) Дан массив целых чисел, в котором все числа встречаются дважды,
а одно не имеет пары, например, (2,3,4,3,2)
Найти это число за линейное время с использованием лишь O(1) памяти
б) А теперь в массиве два непарных числа, например, (1,2,3,1).
Можно ли при тех же ограничениях найти оба числа?

(Alx2 нашел хорошее решение с использованием QuickSort-подобного алгоритма,
однако существует и более простой метод)

6. Многие знают навскидку степени двойки до 2^32 ;)
Может, заметили, что в десятичной системе среди них ни одно число не начинается
с 7-ки. Существуют ли такие 2^N и если да, то как часто встречаются по сравнению с другими начальными цифрами.

7. Дан массив A[0.. 2 * M - 1] of Integer.
Нужно эффективно переставить элементы так, чтобы элементы с четными индексами находились
в начале, с нечетными - в конце, и относительны порядок сохранился
Пример: 0 1 2 3 4 5 6 7 - > 0 2 4 6 1 3 5 7

← →
Юрий Зотов © (2007-11-16 09:07) [1]

Первый раз Вася посылает резиденту сейф с одним ключом A, второй ключ А оставляет себе. Резидент возвращает ему сейф с одним ключом В, второй ключ В оставляет себе. В итоге - сейф у Васи, у него же комплект ключей, у резидента тоже комплект ключей. Все остальные разы сейф пересылается туда-обратно вообще без ключей.

← →
MBo © (2007-11-16 09:15) [2]

>Первый раз Вася посылает резиденту сейф с одним ключом A, второй ключ А оставляет себе. Резидент возвращает ему сейф с одним ключом

если сейф закрыт на A, то резидент не сможет достать ключ из сейфа и положить свой

← →
Юрий Зотов © (2007-11-16 09:17) [3]

> MBo © (16.11.07 09:15) [2]

А ключ при пересылке должен быть обязательно внутри сейфа?

← →
MBo © (2007-11-16 09:18) [4]

>А ключ при пересылке должен быть обязательно внутри сейфа?
Да, иначе почтальоны скопируют

← →
J_f_S (2007-11-16 09:21) [5]

НО допустить копирование одного ключа можно?

← →
Bless © (2007-11-16 09:30) [6]

1) Ложим ключ А в сейф, закрываем на замок А, шлем резиденту.
2) резидент закрывает сейф на замок В, шлет обратно.
3) Открываем замок А (В по-прежнему закрыт), отсылаем обратно резиденту.
4) Резидент открывает замок В, от которого у него есть ключ, и достает ключ А из сейфа, имея полный комплект.

P.S.
Долгих лет жизни Василию!

← →
БарЛог (2007-11-16 09:32) [7]

Первый раз посылаем закрытым только на Б, второй раз - только на А :)
Недостающие ключи - внутри сейфа.

← →
MBo © (2007-11-16 09:43) [8]

>Bless © (16.11.07 09:30) [6]
Верно.
Подобным же образом можно и второй ключ Васе переслать, если возникнет желание.

← →
Anatoly Podgoretsky © (2007-11-16 09:44) [9]

> Bless (16.11.2007 09:30:06) [6]

> Долгих лет жизни Василию!

И как он только не свихнется, каждую неделю такой стресс, все не как у нормальных людей.

← →
KSergey © (2007-11-16 09:52) [10]

Я может чего не секу в стандартах математических задач или в стандартных инструментах резидентов, равно как и "стандарт" в функционировани сейфов, но хотелось бы прочитать о функционировании конкретного сейфа из первой задачи.

У него одно отделение, доступ в которое из 2-х различных дверец? У него одна дверца с двумя замками (открывается только когда оба замка открыты)? у него у него 2 отделения и в каждое своя дверца?

отсюда и ответы слишком разные, т.к. каждый функционирование сейфа понимает по-своему.

← →
KSergey © (2007-11-16 09:56) [11]

> KSergey © (16.11.07 09:52) [10]

лана, если ответ верный есть - то понятно.

← →
oldman © (2007-11-16 09:57) [12]

4.
Лег спать в 23.14
Встал в 8.56
Спал 9 часов 42 минуты.

Плюс-минус несколько минут. Лень точно углы считать.

← →
oldman © (2007-11-16 10:01) [13]

7. По очереди нечетные элементы переставляем в конец списка.
Просто в конец, сдвигая все остальные вверх.
Прикольно, что в цикле надо переставлять элементы 2,3,4,5,6 и т.д...
То есть, в начальном списке 1 занимает второе место, 3 - четвертое, но после перестановки 3 занимает третье место :)))

← →
oldman © (2007-11-16 10:04) [14]

> Bless © (16.11.07 09:30) [6]

То есть четыре раза сейф напрасно катается туда-сюда.
А документы внутри резиденту по фигу?

← →
oldman © (2007-11-16 10:07) [15]

А если ключи есть только у Васи и у резидента на фига ДВА замка???
:))))))))))

← →
palva © (2007-11-16 10:09) [16]

3. Первый метр муха пролетела за одну секунду, второй за 1/2, третий за 1/4, потом будет 1/8 1/16 ... 1/(2^n). Если мы суммируем все эти времена, то получим 2. То есть двух секунд мухе будет достаточно, чтобы пролететь как угодно большое расстояние.

← →
oldman © (2007-11-16 10:11) [17]

> palva © (16.11.07 10:09) [16]

Если ответ правильный, то класс!!!
:)

← →
Jeer © (2007-11-16 10:12) [18]

3. Муха покроет любое расстояние не более чем за 1.3(3) сек.

← →
TUser © (2007-11-16 10:17) [19]

6 было уже. Да, встречаются, статистически столь же часто, как и все остальные.

← →
MBo © (2007-11-16 10:18) [20]

> oldman © (16.11.07 09:57) [12]
14 минут и 8 часов - стрелки не совпадают

>palva © (16.11.07 10:09) [16]
>То есть двух секунд мухе будет достаточно, чтобы пролететь как угодно большое расстояние
точно ;)

>oldman © (16.11.07 10:01) [13]
Придется много раз сдвигать одни и те же элементы.
Быстрее всего, конечно, использовать еще один такой же массив, и скопировать элементы на свои места. Но это расточительно по памяти.
Твой способ передвигает на месте, но имеет квадратичную сложность.
Интересно было бы найти метод перепаковки с минимальным потреблением памяти и как можно быстрее (линейный)

← →
MBo © (2007-11-16 10:19) [21]

> статистически столь же часто, как и все остальные
неверно

← →
oldman © (2007-11-16 10:21) [22]

> MBo © (16.11.07 09:00)
> 7. Дан массив A[0.. 2 * M - 1] of Integer.

Сдается мне, что 0 ... 2*М-1 это массив нечетных чисел.
Или, а что тогда такое М?

← →
MBo © (2007-11-16 10:21) [23]

>Сдается мне, что 0 ... 2*М-1 это массив нечетных чисел.
>Или, а что тогда такое М?
Имеется в виду массив четной длины.

← →
Колхоз (2007-11-16 10:22) [24]

Еще задачки:

> Васе Пупкину поручили организовать сообщение с резидентом
> разведки в некой
> стране.

Как он до "организации сообщения" связался с резедентом, дабы пояснить алгоритм этого самого сообщения ?

> У Васи имеется микросейф с двумя замками A и B и два ключа
> от замка A.

Микро это -6 степень, какимиже должны быть ключи ?

> У резидента есть два ключа от замка B.

Кто передал ключи резеденту ?

> Сейф с документами будет пересылаться
> обычной почтой.

Какова цена документов, если резедент не сможет их прочесть, т.к., сейф -6 степень ?

> Как застраховаться от утечки информации при пересылке сейфа
> туда-сюда?

Можно ли застраховатся при пересылке важных документов, почтой ?

← →
oldman © (2007-11-16 10:23) [25]

> MBo © (16.11.07 10:18) [20]
> > oldman © (16.11.07 09:57) [12]
> 14 минут и 8 часов - стрелки не совпадают

А где будет часовая стрелка в 8:56?

← →
oldman © (2007-11-16 10:32) [26]

7. Можно так:
Для k=1,3,5,...,2*М-3 меняем местами элементы k и k+1
Повторяем, меняя границы...

Пример:
0(12)(34)(56)7
02(14)(36)57
024(16)357
02461357

(ij) - пары перестановок

← →
Bless © (2007-11-16 10:33) [27]

4-я задача.
Вася спал 9 часов , 13 минут плюс 11/13 минуты :)

← →
palva © (2007-11-16 10:33) [28]

> Как он до "организации сообщения" связался с резедентом, дабы пояснить алгоритм этого самого сообщения ?

Нашел адрес резидента через службу "Одноклассники" и открытым текстом договорился с ним о протоколе обмена ключами.
А можно гвоздем на двери сейфа нацарапать послание. Пусть читают, главное, чтоб не стерли.

← →
oldman © (2007-11-16 10:34) [29]

Условие границ неправильно написал... :(

← →
TUser © (2007-11-16 10:38) [30]

> MBo © (16.11.07 10:19) [21]
> > статистически столь же часто, как и все остальные неверно

?

7*10^k<=2^n<8*10^k
ld7+k*ld10<=n<3+k*ld10

Рассмотрим окружность радиуса ld10. Числа из обозначенных интервалов все занимают некоторый участок такой окружности. Шагая по окружности с шагом 1 мы обязательно будем попадать в этот интервал (длина окружности иррациональна). Причем столь же часто, как и во все остальные. Потому что, если мы реже попадаем в этот интервал, чем в среднем, то мы реже попадаем и в интервал с границами, сдвинутыми на единицу, и на 2 и т.д., а в силу иррациональности длины окружности, мы реже попадаем в любую точку окружности, чем в среднем, чего быть не может.

← →
Jeer © (2007-11-16 10:40) [31]

> palva © (16.11.07 10:09) [16]

> 3. Первый метр муха пролетела за одну секунду, второй за
> 1/2,

> MBo © (16.11.07 10:18) [20]

> точно ;)

Я исходил из равномерного ускорения мухи в пределах метра, что естественно для "обычной" физической мухи, а изменение скорости скачком в конце каждого метра посчитал для нее не выполнимым:))

В этом случае:

Первый метр муха пролетит не за 1 сек, т.к. в начале этого метра она имела скорость 1 м/с, а в конце этого метра уже 2 м/c
Следовательно, средняя скорость мухи на первом метре равна (1 + 2)/2 = 1.5 м/с
Отсюда очевидно, что время пролета первого метра dT = S/Vср = 1/1.5 = 2/3 с

Рассуждая аналогично определим, что на втором метре средняя скорость равна Vср = (2 + 4)/2 = 3 м/c и время dT = 1/3 = 2/6

И так далее.

Т.е. мы имеем прогрессию T = 2/3 + 2/6 + 2/12 + ... которая имеет пределом именно 1.3(3)

← →
palva © (2007-11-16 10:42) [32]

Jeer © (16.11.07 10:40) [31]
Ну да, принцип тот же, только цифры немного другие.

← →
oldman © (2007-11-16 10:44) [33]

> Jeer © (16.11.07 10:40) [31]

Читаем условие:

> каждый раз, пролетая еще один метр, она удваивала скорость.

Видимо таки скачком...
:)))

← →
oldman © (2007-11-16 10:45) [34]

> palva © (16.11.07 10:42) [32]
> Jeer © (16.11.07 10:40) [31]
> Ну да, принцип тот же, только цифры немного другие.

Твой-то ответ тоже правильный.
При пределе1,3(3) двух секунд ей за глаза, чтоб пролететь сколько хочет...

← →
Jeer © (2007-11-16 10:49) [35]

> oldman © (16.11.07 10:44) [33]
>
>

> Читаем условие:
>
>
> > каждый раз, пролетая еще один метр, она удваивала скорость.
>

Условие скачка нечетко выражено.

> > каждый раз, пролетая еще один метр, она скачком удваивала скорость.

Здесь нет вопросов.

"Богат могучим русский языка"

← →
Vlad Oshin © (2007-11-16 10:56) [36]

1.
послали сейф - 1
не послали - 0
и так передать все что надо сказать. А ключи выкинуть нафиг

← →
oldman © (2007-11-16 11:00) [37]

> Vlad Oshin © (16.11.07 10:56) [36]

Это-ж только на фразу "Юстас Алексу" сейфов не напасешься...

← →
guav © (2007-11-16 11:20) [38]

5. а)

function FindUnmatched(const A: array of Integer): Integer; var I := 0; begin Result := 0; for I := Low(A) to High(A) do begin if Result > A[I] then Result := Result - A[I] else Result := Result + A[I]; end; end;

PS: Интересно, скомпилится ли вообще, давно на Delphi не писал и сейчас проверить не на чём.

← →
Sha © (2007-11-16 11:35) [39]

> guav © (16.11.07 11:20) [38]

xor проще

← →
guav © (2007-11-16 11:40) [40]

> [39] Sha © (16.11.07 11:35)

Точно, не подумал.
Зато так будет работать и с Double :)

> var I := 0;

конечно же
var I: Integer;

← →
ЮЮ © (2007-11-16 11:48) [41]

> [38] guav © (16.11.07 11:20)

> PS: Интересно, скомпилится ли вообще, давно на Delphi не
> писал и сейчас проверить не на чём.

И без Дельфи видно, что у тебя получится неправильно: 3 сложил дважды, а 4 и вовсе вычел.
2 + 3 - 4 + 3 - 2

← →
guav © (2007-11-16 11:50) [42]

> [41] ЮЮ © (16.11.07 11:48)

Угу :(

← →
Sha © (2007-11-16 11:53) [43]

5б аналогично.

На первом проходе XOR-ом отыскиваем бит, в котором наши числа не совпадают.
На втором проходе вычисляем XOR0 для всех чисел, содержащих 0 в этом бите, и XOR1 для чисел, содержащих 1.
Это и будут искомые числа.

2. 21 круг?

>Вася спал 9 часов , 13 минут плюс 11/13 минуты :)
Да

>Sha © (16.11.07 11:53) [43]
точно )

>21 круг?
Да

>Jeer
ОК, можно и так интерпретировать.

>oldman © (16.11.07 10:32) [26]
Так уже быстрее, но алгоритм все равно квадратичный (количество обмениваемых пар - убывающая арифм. последовательность)

> Jeer © (16.11.07 10:49) [35]
> > каждый раз, пролетая еще один метр, она скачком удваивала скорость.

через 1.33 сек качок начал отставать :)
"Богат могучим русский языка"

> 7. Дан массив A[0.. 2 * M - 1] of Integer.
> Нужно эффективно переставить элементы так, чтобы элементы
> с четными индексами находились
> в начале, с нечетными - в конце, и относительны порядок
> сохранился
> Пример: 0 1 2 3 4 5 6 7 - > 0 2 4 6 1 3 5 7

Методически задача решается просто:

Разделение массива на упорядоченные части не что иное как сортировка разных по качеству данных в пределах своего класса и сортировка классов.

Предположим, что четные числа занимают класс "легкие", а нечетные - класс "тяжелые".
В таком случае, всем известный и любимый метод пузырька с небольшой модификацией сепарации данных легко разделит "масло" и "воду".
Аналогично, сработают и все другие методы сортировки.
Т.е. можно получить желаемый вид О(f(N).

Приведу два крайних случая для сложности алгоритма N^2 и N и расхода дополнительной памяти M(1) и M(N):

"Пузырек"
n := Length(ar) div 2;
k := 1;
for j:=1 to n-1 do begin
m:=k;
for i:= 1 to n-k do begin
x := ar[m];
ar[m] := ar[m+1];
ar[m+1] := x;
m := m + 2;
end;
Inc(k);
end;

"Разделение и слияние"
n := Length(ar) div 2;
SetLength(ar1,n);
SetLength(ar2,n);
for i:=0 to n-1 do begin
j := i*2;
ar1[i] := ar[j];
ar2[i] := ar[j + 1];
end;
for i:=0 to n-1 do begin
ar[i] := ar1[i];
ar[n+i] := ar2[i];
end;

> oldman © (16.11.07 19:12) [49]
> Jeer © (16.11.07 15:46) [48]

Есть еще вариант с прямым циклическим обменом,
например, для массива:

0 1 2 3 4 5 6 7 - > 0 2 4 6 1 3 5 7

первый (и единствееный) цикл такой:

1 -> temp
2 -> 1
4 -> 2
1 -> 1

-----

Для 10 элементов требуется уже 2 цикла обмена.
И вот здесь пока не видно простого перехода к следующему циклу, кроме как хранить историю.

Там опечатка, так, конечно:

1 -> temp
2 -> 1
4 -> 2
temp -> 1

И еще одна неточность - в примере требуется и второй цикл:

3 -> temp
6 -> 3
5 -> 6
temp -> 5

На работе инет отвалился. Не успел выложить. :( Но все-таки несмотря на то что решение уже огласили в 39 приведу пример реализации.
const Len=5; arr:array[1..Len] of integer= (2,3,4,3,2) ; var i,x:integer; begin x:=0; for i:=1 to Len do x:=x xor arr[i]; Memo1.Lines.Add("Ответ: "+inttostr(x)); end;
Для произвольного числа неповторяющихся элементов лучшее что я знаю - это отсортировать их (n log(n)) и пройтись один раз выбираяя уникальные элементы.

7. наиболее быстро (два прохода) с вспомогательным массивом. просто копируем туда элементы. Первый проход выясняем количество четных (NPos). При втором проходе копируем четные с начала а нечетные с позиции NPos;

>осталось проверить работает ли это оптимальнее [26]
>MBo молчит почему-то...

Квадратичные алгоритмы не требуют доп. памяти, очень просты, и неплохо работают для небольших массивов, но для размера, например, миллион - непригодны, там
нужны алгоритмы с линейной сложностью (или хотя бы N Log N), но в данном случае они, похоже, неизбежно требуют дополнительной памяти, сравнимой по размеру с исходным массивом (самый быстрый способ, конечно - завести массив такого же размера, и скопировать элементы на свои места)

>vpbar © (16.11.07 20:16) [54]
Не значения элементов важны, а индексы. Пример - из массива пар (X, Y) получить массив, в котором вначале иксы идут, потом игреки.

Вот что я делал для [7], та же идея, что в Sha © [50].
Пытался найти закономерности для стартовых индексов цепочек обменов - не получилось, пришлось с массивом битовых флагов (дополнительная память для массива 2*M чисел - M/8 байт). Можно TBits использовать, чтобы код не загромождать.

procedure ReArrange(var A: array of Integer);//длина массива - четное число var i, t, istart, ifrom, ito, N, iused, ibyte, ibit: Integer; Used: array of Byte; function FromIndx(Ix: Integer): Integer; // c какого индекса копировать в индекс Ix begin if Ix < Middle then Result := 2 * Ix else Result := (Ix - Middle) * 2 + 1; end; begin N := Length(A); Middle := N div 2; SetLength(Used, (Middle + 7) div 8); // массив битовых флагов для нечетных индексов, автоинициализируется нулями for iused := 0 to Middle div 2 - 1 do if Used[iused shr 3] and (1 shl (iused and 7)) = 0 then begin // если этот элемент еще не участвовал в перестановках istart := iused * 2 + 1; ito := istart; t := A[istart]; ifrom := FromIndx(istart); while ifrom <> istart do begin if (ito < Middle) and ((ito and 1) = 1) then begin ibyte := ito shr 4; ibit := (ito shr 1) and 7; Used[ibyte] := Used[ibyte] or (1 shl ibit); // помечаем, что элемент участвовал в перестановках end; A[ito] := A[ifrom]; ito := ifrom; ifrom := FromIndx(ito); end; A[ito] := t; end; end;

Нда. Подвел пример и невнимательное чтение условия. :)
Наиболее быстро но требует дополнительно М памяти для массива длиной 2М
procedure TForm1.Button3Click(Sender: TObject); const Len = 8; arr: array[0..Len] of integer = (0, 1, 2, 3, 4, 5, 6,7 ,8); procedure dooArr(var a: array of integer); var I,J,K, L, StartIdx, InsIdx, EndIdx: INteger; siteOfTempArray: integer; t: array of integer; begin StartIdx := Low(a); EndIdx := High(a); L := EndIdx - StartIdx + 1; siteOfTempArray := L div 2; SetLength(t, siteOfTempArray); InsIdx := StartIdx; // для массивов которые индексируются не с 0 // if StartIdx mod 2 = 0 then // begin // если первый индекс четный // inc(StartIdx,2); // inc(InsIdx) // end // else // begin // если первый индекс нечетный // inc(StartIdx); // end; inc(StartIdx,2); inc(InsIdx); J:=0; K:=InsIdx; (*1*) while InsIdx<= EndIdx do // запоминаем нечетные begin t[J]:=a[InsIdx]; inc(InsIdx,2); inc(J); end; (*2*) while StartIdx<= EndIdx do //перемещаем четные begin a[K]:=a[StartIdx]; inc(StartIdx,2); inc(K); end; // в принципе циклы *1* и *2* можно объединить J:=0; while K<= EndIdx do // копируем четные пожно movemem begin a[K]:=t[J]; inc(J); inc(K); end; end; begin dooArr(arr); OutArr(arr); end; procedure TForm1.OutArr(arr: array of integer); var I: INteger; s: string; begin s := ""; for I := Low(Arr) to High(Arr) do s := s + inttostr(arr[i]) + ","; Memo1.Lines.Add(s); end;

Воот. решение для 7й задачи сложность примерно N-3
procedure TForm1.Button4Click(Sender: TObject); function NewIdx(idx, L: integer): integer; // возвращает новую позицию begin if Odd(idx) then // если нечетный result := (L - L div 2) + idx div 2 else // если четный result := idx div 2; end; procedure dooArr(var a: array of integer); var i, t, b, nIdx, LastC, L, first, N: integer; begin L := High(a) - Low(a) + 1; LastC := (L-1) div 2 ; // индек последнего четного элемента; first := 1; nIdx := first; I := 0; t := a[nIdx]; N := 0; repeat nIdx := NewIdx(nIdx, L); b := a[nIdx]; a[nIdx] := t; t := b; if nIdx = first then begin while I <= LastC do begin if odd(a[I]) then break; inc(I); end; if I>LastC then begin Memo1.Lines.Add("N:" + inttostr(N)); exit; end; first := i; nIdx := first; t := a[nIdx]; end; inc(N); until false; end; var i: integer; arr: array of integer; begin SetLength(arr, SpinEdit1.Value); for i := 0 to SpinEdit1.Value - 1 do arr[i] := i; // OutArr(arr); Memo1.Lines.Add("==========================="); dooArr(arr); Memo1.Lines.Add("--------------------------"); // OutArr(arr); end;

Я знал что можно проще :)

>vpbar © (17.11.07 19:21) [57]

а что будет, если заполнение массива сделать так:
for i := 0 to n - 1 do
arr[i] := i + 1;

Должно быть: 1 2 3 4 5 6 7 8 -> 1 3 5 7 2 4 6 8
Еще раз скажу, что значения несущественны (это могуть быть, например, строки, вещ. числа или составные структуры), главное, чтобы элементы, которые были на четных местах, собрались в начале
Так что проверка if odd(a[I]) - зря.

> MBo © (18.11.07 12:30) [58]

блин. :( опять ступил. Прошу прощения.
Е
> Еще раз скажу, что значения несущественны

Это я понял. Просто упустил из внимания. Обрадовался, что работает и поспешил выложить.
Все таки потребуется память. Битовый массив из M бит чтобы хранить какие элементы уже переставлены.

Опять про перестановку:
01234567 (N элементов)

За один проход (N/2 перестановок) можно добиться того, что четные стоят по порядку, а нечетные нет. Сами понимаете, что за меньшее количество перестановок этого добиться нельзя.
Осталось быстро сортануть вторую половину массива.

Кстати, в варианте со вторым массивом на миллион элементов - миллион перестановок :)))

>Осталось быстро сортануть вторую половину массива.
Сортировать по значениям нельзя

Ну а нечетную половину пузырьком.
Так можно?

Пятничные задачки. Вася Пупкин еще жив ;) Найти похожие ветки