Занимательные задачи

← →
Oleg_Gashev © (2002-10-12 18:27) [0]

Здравствуйте!

Тема задач многим нравится на этом форуме. Поэтому вот Вам две:

1) Есть числа от 1 до N. Вывести их случайным образом, без повторений. 2) Вывести все инволюции множества {1,2,3,...,N}.

Успехов.

← →
Romkin © (2002-10-12 19:01) [1]

2 - Д.Кнут т3 5.1.4 %-)) - считается ли это решением?
Меня больше привлекают немного другие задачи, одна из подобных есть в книге Jon Bentley "Programming Pearls":
3. Имеется файл, содержащий 7-значные телефонные номера (для простоты - текстовый, один номер в строке). Понятно, что номеров не более 10000000, они не повторяются. Нужно выдать файл с теми же номерами, отсортированными по фозрастанию, причем оперативной памяти использовать не более 2 Мб :-)), и как можно быстрее, в идеале за время от 10 сек до пары минут.
Вся изюминка в том, что когда есть решение, понимаешь, насколько оно элементарно.

← →
Anatoly Podgoretsky © (2002-10-12 19:14) [2]

Тот же Кнут, у него приведены алгоритмы для файлов с очень небольшим использованием памяти, если не ошибаюсь то метод слияния.

← →
Romkin © (2002-10-12 19:35) [3]

Прошу учесть, что файл с номерами занимает около 85 Мб, и на одно его считывание требуется несколько секунд (в лучшем случае, у меня копирование прошло за 20 сек, а диск довольно быстрый). При сортировке слиянием памяти, конечно, требуется немного, но вот считано/записано будет примерно раз в 20 больше. Я ожидаю, что это займет примерно 10 минут в лучшем случае, а это не слишком приятно. Мне бы хотелось увидеть решение, которое сделает то же самое за время, не намного большее, чем простое копирование файла

← →
down (2002-10-13 11:27) [4]

Как насчет такого алгоритма:
1.Выводим в текстовый файл все возможные номера по порядку,
к каждому номеру справа добавляем пробел
2.Последовательно читаем файл с номерами, каждый прочитанный номер отмечаем в созданном файле (позицию номера в файле знаем, отмечаем, например, заменой пробела на "+")
3.Последовательно читаем созданный файл, если номер отмечен, то
записываем его в другой файл, это и будет результат

← →
TTCustomDelphiMaster © (2002-10-13 11:52) [5]

Romkin

1. Резервируем память 10000000 бит. (чуть больше 1 Мб)
2. Читаем из файла номера и включаем биты с соответствующим номером.
3. Проверяем в цикле биты. Если включен, записываем его номер в файл.

← →
Romkin © (2002-10-13 11:53) [6]

2TTCustomDelphiMaster Ты знал, ты знал! %-))

← →
TTCustomDelphiMaster © (2002-10-13 11:56) [7]

Только что придумал :)

← →
Romkin © (2002-10-13 12:03) [8]

Просто изюминка этой задачи в том, что все начинают подбирать подходящий метод сортировки...
2down
Насколько понимаю, этот метод тоже подходит, он практически идентичен TTCustomDelphiMaster © (13.10.02 11:52)
Вот только битовый массив в отличие от файла полностью в памяти :-))

← →
Forever (2002-10-13 13:24) [9]

Читаем из файла номера и включаем биты с соответствующим номером.

Можно поподробнее ?

← →
TTCustomDelphiMaster © (2002-10-13 14:02) [10]

Допустим прочитали из файла номер 1234567.
Включаем бит с номером 6 (1234567 mod 8 = 7) в 154320-м байте (1234567 div 8 = 154320).

На самом деле все немного сложнее. Во первых телефонов с номерами 0 - 999999 не существует (не считая справочных) и памяти можно резервировать на 10 процентов меньше при этом из номера нужно вычитать 1000000. Во вторых вместо операций div и mod применяется смещение битов shl это будет быстрее.

← →
down (2002-10-13 14:58) [11]

2TTCustomDelphiMaster
Идейка-то моя, моя... :)

← →
TTCustomDelphiMaster © (2002-10-13 15:11) [12]

down

Претендуете на нобелевскую :)

← →
down (2002-10-13 15:21) [13]

Удалено модератором

← →
Romkin © (2002-10-13 16:03) [14]

Задача № 1.
program GenRec; {$APPTYPE CONSOLE} uses Windows, SysUtils; const minPhone = 1000000; maxPhone = 9999999; type TPhoneRec = packed record Phone: string[7]; Name: string[50]; end; TPhoneSortRec = record Rnd: Double; Phone: integer; end; TPhoneSort = array [minPhone .. maxPhone] of TPhoneSortRec; procedure QuickSort(var A: TPhoneSort; iLo, iHi: Integer); var Lo, Hi: Integer; Mid: Double; T: TPhoneSortRec; begin Lo := iLo; Hi := iHi; Mid := A[(Lo + Hi) div 2].Rnd; repeat while A[Lo].Rnd < Mid do Inc(Lo); while A[Hi].Rnd > Mid do Dec(Hi); if Lo <= Hi then begin T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T; Inc(Lo); Dec(Hi); end; until Lo > Hi; if Hi > iLo then QuickSort(A, iLo, Hi); if Lo < iHi then QuickSort(A, Lo, iHi); end; var PhoneSort: TPhoneSort; PhoneFile: file of TPhoneRec; i: integer; StartTime, EndTime: DWORD; ANum: double; Sorted: boolean; FileName: string; PhoneRec: TPhoneRec; begin // gen phone numbers writeln("Phone numbers generating..."); StartTime := GetTickCount; randomize; for i := minPhone to maxPhone do with PhoneSort[i] do begin Phone := i; Rnd := random; end; EndTime := GetTickCount; writeln("Generation complete. Time is ", (EndTime - startTime)/1000, " sec"); writeln("Random sorting..."); StartTime := GetTickCount; QuickSort(PhoneSort, minPhone, maxPhone); EndTime := GetTickCount; writeln("Sort complete. Time is ", (EndTime - startTime)/1000, " sec"); writeln("Check sorting..."); StartTime := GetTickCount; ANum := PhoneSort[minPhone].Rnd; Sorted := true; for i := minPhone + 1 to maxPhone do if ANum > PhoneSort[i].Rnd then Sorted := false; EndTime := GetTickCount; write("Check complete. Time is ", (EndTime - startTime)/1000, " sec Result is "); if Sorted then writeln("sorted") else writeln("UNsorted!!!"); write("press <Enter> for file generation"); readln; writeln("Record file..."); StartTime := GetTickCount; FileName := IncludeTrailingPathDelimiter(ExtractFilePath(paramStr(0))) + "PhoneRec.dat"; assignFile(PhoneFile, FileName); rewrite(PhoneFile); try for i := minPhone to maxPhone do begin with PhoneRec do begin Phone := IntToStr(PhoneSort[i].Phone); Name := IntToStr(i) + " Time is " + TimeToStr(Now) + " John Dow"; end; Write(PhoneFile,PhoneRec); if (i mod 100000) = 0 then writeln("Writes: ", IntToStr(i - minPhone)); end; finally CloseFile(PhoneFile); end; EndTime := GetTickCount; writeln("Recording complete. Time is ", (EndTime - startTime)/1000, " sec"); write("press <Enter>"); readln; end.
%-)))))))))))))))
Требует примерно 150 Мб оперативки Ж-)

← →
Forever (2002-10-13 16:09) [15]

TTCustomDelphiMaster, не понял. Ну включил биты.
А где сортировка ? Ведь телефоны то по возрастанию нужно отсортировать...

← →
Romkin © (2002-10-13 16:19) [16]

А когда массивбитов проходишь последовательно, в выходной файл пишешь номер бита, если он взведен - это и есть номер телефона, они получатся по возрастанию %-)) И только те, которые есть в исходном файле. Задача решена.
А кто говорил, что нужно обязательно сортировать?

← →
TTCustomDelphiMaster © (2002-10-13 16:19) [17]

...
for i:=0 to 10000000 do // Вот и сортировка :)
if GetBit(i) then
writeln(f, inttostr(i));
...

function GetBit(i: integer): boolean; проверяет i-ый бит.

← →
Forever (2002-10-13 16:28) [18]

А почему они по возрастанию получаются ?

Потому что в цикле for I по порядку нарастает!!!!

Классическое решение задачи 1:
вывод в файл, так удобнее
program Rnd1toN; {$APPTYPE CONSOLE} uses SysUtils; const N = 2500; type TMySort = array [1..N] of integer; var MySort: TMySort; i, k, T: integer; FileName: string; MyFile: textFile; begin writeLn("Enter the name of result file, please: "); readln(FileName); assignFile(MyFile,FileName); rewrite(MyFile); try //initialization for i := 1 to N do MySort[i] := i; randomize; //main block for i := 1 to N do begin k := random(N - i + 1) + i; T := MySort[i]; MySort[i] := MySort[k]; MySort[k] := T; end; //write result for i := 1 to N do writeln(MyFile, IntToStr(MySort[i])); finally closeFile(MyFile); end; writeln("Done!"); readln; end.

Давай для интереса приведи решение с TBits простое и экономичное, для отсортированного списак телефонов от "0000000" до "9999999", то о чем в чате говорили.
Интересно многим будет

Первую задачу можно решить по принципу волчка из передачи "что-где-когда". Заполняем массив числами от 1 до N. Выбираем случайно число. На его место записываем пусто, а число выводим. Если в выбраном месте пусто, то двигаемся по стрелке.

Пока писал первый вариант, придумал еше один.
Заполняем массив числами от 1 до N. Выбираем случайно число. На место выбранного перекладывается число из конца массива, и размер массива уменьшается на 1.

Типа:

var M: of integer; i:integer; ... setlength(M,N-1); randomize; while Length(M)>0 then begin i:=int(Random(Length(M)-1)); writeln(F,M[i]); M[i]:=M[length(M)-1] setlength(M,length(M)-1); end;

Типа да, только размер массива не надо уменьшать каждый раз. Достаточно уменьшать значение переменной в которой записана его длина.

У меня было похожее решение первой задачи. Инициализируем масив A[i]:=i и пробегаем все элементы масива подряд, меняя каждый элемент масива с элементом, выбранным случайным образом.

program Rnd1toN;
{$APPTYPE CONSOLE}
uses SysUtils;

const
N = 2500;

type
TMySort = array [1..N] of integer;

var
MySort: TMySort;
i, k: integer;
FileName: string;
MyFile: textFile;

begin
writeLn("Enter the name of result file, please: ");
readln(FileName);
assignFile(MyFile,FileName);
rewrite(MyFile);
try
randomize;
for i := N downto 1 do
MySort[i] := i;
for i := N downto 1 do
begin
k := random(i) + 1;
writeln(MyFile, IntToStr(MySort[k]));
MySort[k] := MySort[i];
end;
finally
closeFile(MyFile);
end;
writeln("Done!");
readln;
end.

Занимательные задачи Найти похожие ветки