Задачи, советы и ответы - часть 11

cout << (unsigned int)w.ti_hund << endl;

bubble(num,MAX);

//select(num,MAX);

//insert(num,MAX);

//shell(num,MAX);

//hoare(num,MAX);

gettime(&w);

cout << (unsigned int)w.ti_sec <<".";

cout << (unsigned int)w.ti_hund << endl;

//cout << "Кончили";

getch();

//for(i=0; i<MAX; i++)

//cout << num[i] << " ";

//getch();

return 0; }

/*==== тестируемые процедуры ========*/

Программа 4_07.pas

program all_sort; uses crt,WinDos; const

MAX=15000; type

xarr=array [0..MAX-1] of integer; var

x:xarr;

i:integer;

hour,minute,second,sec100:word;

{===== тестируемые процедуры ======}

begin

clrscr;

for i:=0 to MAX-1 do

begin

x[i]:=random(MAX); {write(x[i],' ');}

end;

writeln;

write('До сортировки - ');

gettime(hour,minute,second,sec100);

write(minute:2,' мин ',second:2,'.',sec100:2, ' сек');

writeln;

{Вызов метода}

{ bubble(x,MAX);}

{ select(x,MAX);}

{ insert(x,MAX);}

shell(x,MAX);

{ hoare(x,MAX);}

gettime(hour,minute,second,sec100};

write('После сортировки - ');

write(minute:2,' мин ',second:2,'.',seclOO:2,' сек');

writeln;

{ for i:=0 to MAX-1 do write(x[i],' ');}

readln; end.

Задание 4.08. Счастливый билет

Билет с шестизначным цифровым номером считается "счастливым", если сумма трех старших цифр совпадает с суммой трех младших цифр. В предположении, что в билетной кассе находится миллион билетов с номерами от 000000 до 999999, надо определить количество потенциально осчастливленных пассажиров.

Совет 1 (общий)

Алгоритм "в лоб" заключается в том, чтобы организовать шесть вложенных циклов, в каждом из которых перебирается очередная цифра номера. В самом внутреннем цикле организуется проверка суммы старших и младших цифр номера и подсчет счастливых билетов. Однако эту проверку придется повторять миллион раз, и даже достаточно мощные процессоры затратят на такой алгоритм заметное время. Решение задачи можно найти примерно в 1000 раз быстрее, если вместо лобового перебора подсчитать, сколько раз сумма трех цифр равна 0, 1, 2.....27. Очевидно, что нулевую сумму дает единственная комбинация цифр 000, представляющая единственный счастливый билет с номером 000000. Сумму, равную 1, дают три комбинации — 001, 010 и 100. Соответственно, счастливых билетов с такой суммой уже 9 (каждая из перечисленных выше комбинаций в старших цифрах с тремя аналогичными сочетаниями в младших разрядах). Таким образом, если обозначить через s [0], s [1].....S [27] количество комбинаций цифр, сумма которых равна индексу элемента в массиве S, то общее количество счастливых билетов N будет равно сумме:

Содержание  Назад  Вперед

---

---

---