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

← →
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.
Это и будут искомые числа.

← →
Agent13 © (2007-11-16 11:53) [44]

2. 21 круг?

← →
MBo © (2007-11-16 12:58) [45]

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

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

>21 круг?
Да

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

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

← →
Petr V. Abramov © (2007-11-16 13:38) [46]

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

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

← →
Jeer © (2007-11-16 14:13) [47]

> Petr V. Abramov © (16.11.07 13:38) [46]

> качок начал отставать

:)) +5

← →
Jeer © (2007-11-16 15:46) [48]

> 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 © (2007-11-16 19:12) [49]

> Jeer © (16.11.07 15:46) [48]

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

← →
Sha © (2007-11-16 19:44) [50]

> 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 цикла обмена.
И вот здесь пока не видно простого перехода к следующему циклу, кроме как хранить историю.

← →
Sha © (2007-11-16 19:45) [51]

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

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

← →
Sha © (2007-11-16 19:51) [52]

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

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

← →
vpbar © (2007-11-16 20:12) [53]

На работе инет отвалился. Не успел выложить. :( Но все-таки несмотря на то что решение уже огласили в 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)) и пройтись один раз выбираяя уникальные элементы.

← →
vpbar © (2007-11-16 20:16) [54]

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

← →
MBo © (2007-11-17 12:54) [55]

>осталось проверить работает ли это оптимальнее [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 перестановок) можно добиться того, что четные стоят по порядку, а нечетные нет. Сами понимаете, что за меньшее количество перестановок этого добиться нельзя.
Осталось быстро сортануть вторую половину массива.

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

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

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

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