Тема:
Все темы
>>
Комбинаторика
>>
Классическая комбинаторика
>>
Перестановки и подстановки
>>
Перестановки и подстановки (прочее)
Фильтр
Выбрано 3 задачи Убрать все задачи
Можно ли разлить 50 л бензина по трём бакам так, чтобы в первом баке было на 10 л больше, чем во втором, а после переливания 26 л из первого бака в третий в третьем баке стало бы столько же бензина, сколько во втором?
Решение(Э. Дейкстра) Добавим в алгоритм Евклида дополнительные переменные u, v, z:
m := a; n := b; u := b; v := a;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; v := v + u;
| end else begin
| | n := n - m; u := u + v;
| end;
end;
if m = 0 then begin
| z:= v;
end else begin {n=0}
| z:= u;
end;
Доказать, что после исполнения алгоритма значение z
равно удвоенному наименьшему общему кратному
чисел a, b:
z = 2 . НОК(a, b).
РешениеВ колоде часть карт лежит рубашкой вниз. Время от времени Петя вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой верхняя и нижняя карты лежат рубашкой вниз, переворачивает всю пачку как одно целое и вставляет её в то же место колоды (если "пачка" состоит лишь из одной карты, то требуется только, чтобы она лежала рубашкой вниз). Докажите, что в конце концов все карты лягут рубашкой вверх, как бы ни действовал Петя.
Решение
Задачи
Задача 78489 |
|
|
Завод выпускает погремушки в виде кольца с надетыми на него тремя красными и семью синими шариками. Сколько различных погремушек может быть выпущено? (Две погремушки считаются одинаковыми, если одна из них может быть получена из другой только передвижением шариков по кольцу и переворачиванием.)
|
|
Решение |
Задача 35561 |
|
|
Некто расставил в произвольном порядке 10-томное собрание сочинений. Назовём беспорядком пару томов, для которых том с большим номером стоит левее. Для данной расстановки томов посчитано число S всех беспорядков. Какие значения может принимать S?
|
|
|
Решение |
Задача 66350 |
|
|
В зале стоят шесть стульев в два ряда – по три стула в каждом, один ряд ровно за другим. В зал пришли шесть человек различного роста.
Сколькими способами можно рассадить их так, чтобы каждый человек, сидящий в первом ряду, был ниже человека, сидящего за ним?
|
|
|
Решение |
Задача 105076 |
|
|
В колоде часть карт лежит рубашкой вниз. Время от времени Петя вынимает из колоды пачку из одной или нескольких подряд идущих карт, в которой верхняя и нижняя карты лежат рубашкой вниз, переворачивает всю пачку как одно целое и вставляет её в то же место колоды (если "пачка" состоит лишь из одной карты, то требуется только, чтобы она лежала рубашкой вниз). Докажите, что в конце концов все карты лягут рубашкой вверх, как бы ни действовал Петя.
|
|
|
Решение |
Задача 35181 |
|
|
За круглым столом совещались 2n депутатов. После перерыва эти же 2n депутатов расселись вокруг стола, но уже в другом порядке.
Доказать, что найдутся два депутата, между которыми как до, так и после перерыва сидело одинаковое число человек.
|
|
|
Решение |
Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 61]
