Сначала рассмотрим такую задачу: “Имеется некоторое количество рыб. Определить, возможен ли дележ рыб между тремя рыбаками в соответствии с условием задачи Дирака”[1] .
В программе решения этой задачи используем следующие величины:
k0 - общее количество пойманных рыб;
k - количество рыб, оставшееся тому или иному рыбаку;
take - количество рыб, которые взял тот или иной рыбак;
i - номер рыбака;
partit - величина логического типа, определяющая возможность дележа (взятия каждым рыбаком трети оставшегося количества рыб).
На */школьном алгоритмическом языке /*соответствующая программа имеет вид:
_алг_ Available_partition
_нач_ _цел_ k0, k, take, i, _лог_ partit
¦ _вывод_ _нс_, "Введите количество рыб"
¦ _ввод_ k0
¦ k:=k0
¦ i:=1
¦ _нц_ |цикл “действий” каждого рыбака
¦ ¦ k:=k-1 | осталось после выбрасывания одной рыбы
¦ ¦ _если_ mod(k,n)=0
¦ ¦ ¦_то_ | i-й рыбак может взять треть оставшихся рыб
¦ ¦ ¦ partit:=_да_
¦ ¦ ¦ take:=div(k,3) | берет i-й рыбак
¦ ¦ ¦ k:=k- take | оставшееся количество рыб
¦ ¦ ¦_иначе_
¦ ¦ ¦ partit:=_нет_ | при k0 рыбах дележ невозможен
¦ ¦ _все_
¦ ¦ i:=i+1
¦ _кц___при_ i>n _или_ _не_ partit
¦ _если_ partit
¦ ¦_то_
¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ возможен"
¦ ¦_иначе_
¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ невозможен"
¦ _все_
_кон_
После этого программа нахождения минимального количества рыб, удовлетворяющего условию задачи Дирака, может быть оформлена очень кратко:
_алг_ Задача_Рыбаки_и_рыбки
_нач_ _цел_ k0
¦ k0:=0 |начальное значение диапазона поиска
¦ _нц_ _пока_ _не_ Avail_partit (k0)
¦ ¦ k0:=k0+1 |очередное значение
¦ _кц_
¦ _вывод_ _нс_, "Наименьшее количество рыб,"
¦ _вывод_ "удовлетворяющее условию задачи:", k0
_кон_
где Avail_partit(k0) - вс функция логического типа, определяющая возможность дележа k0/ /рыб в соответствии с условием задачи, составленная на основе программы, приведенной чуть выше:
алг_ _лог_ Avail_partit (_арг_ _цел_ k0)
_нач_ _цел_ k, take, i, _лог_ partit
¦ k:=k0
¦ i:=1
¦ _нц_
¦ ¦ k:=k-1
¦ ¦ _если_ mod(k,3)=0
¦ ¦ ¦_то_
¦ ¦ ¦ partit:=_да_
¦ ¦ ¦ take:=div(k,3)
¦ ¦ ¦ k:=k- take
¦ ¦ ¦ _иначе_
¦ ¦ ¦ partit:=_нет_
¦ ¦ _все_
¦ ¦ i:=i+1
¦ _кц___при_ i>3 _или_ _не_ partit
¦ _знач_:= partit | значение функции
_кон_
Соответствующая программа на Паскале:
{Задача “Рыбаки и рыбки”}
Var
k0: integer;
Function Avail_partit (k0: integer): boolean;
Var
k, take, i: integer;
partit: boolean;
begin
k:=k0;
i:=1;
repeat {цикл “действий” каждого рыбака}
k:=k-1; {осталось после выбрасывания одной рыбы}
if k mod 3 = 0 then
{i-й рыбак может взять треть оставшихся рыб}
begin
partit:=true;
take:=k div 3; {берет i-й рыбак}
k:=k - take {оставшееся количество рыб}
end
else
partit:=false; {дележ невозможен}
i:=i+1
until (i>3) or not partit;
Avail_partit:= partit {значение функции}
end;
BEGIN {Основной программы}
k0:=0; {начальное значение диапазона поиска}
while not Avail_partit(k0) do
k0:=k0+1; {очередное значение}
write('Наименьшее количество рыб, ');
writeln('удовлетворяющее условию задачи: ', k0)
END.
Выполнив программу, можно увидеть, что минимальное количество рыб, удовлетворяющее условию задачи, равно 25. Имеются и большие значения (52, 79, 106, ...).
Имеется и другой решения задачи. Можно, так сказать, идти не от общего количества пойманных рыб, а от числа рыб, доставшихся третьему рыбаку. Если эту величину обозначить take3, то можно записать, что количество рыб, оставшееся тому или иному рыбаку, равно:
1) третьему рыбаку: k3 = 3* take3 + 1;
2) второму: k2 = 3*k3 + 1;
3) первому (то есть общее количество пойманных рыб[2]): k1 = 3*k2 + 1.
Перебирая значения k3, равные 1, 2, 3, …, можно найти такое минимальное число, при котором значения величин k2 и k1 есть целые числа.
Программа, реализующая такой подход к решению задачи, имеет вид:
Рассмотренную задачу можно решать и при другом числе рыбаков. Соответствующие результаты представлены в таблице (естественно, что некоторые из них являются условными).
Смотри, для перевода из восьмеричной в десятичную надо это число представить в виде суммы произведения основания восьмеричной системы счисления на соответствующие цифры в разрядах восьмеричного числа:
К примеру, возьмем число 2357, нужно перевести в десятичную, в этом числе 4 цифры и 4 разряда (Разряды считаются, начиная с нулевого которому соответствует младший бит), в соответствии уже с известным правилом представим его в виде суммы степеней с основанием 8:
Для вычислений "вручную" и решения примеров и контрольных заданий вам могут пригодиться таблицы степеней оснований изучаемых систем счисления (2, 8, 10, 16)
Сначала рассмотрим такую задачу: “Имеется некоторое количество рыб. Определить, возможен ли дележ рыб между тремя рыбаками в соответствии с условием задачи Дирака”[1] .
В программе решения этой задачи используем следующие величины:
k0 - общее количество пойманных рыб;
k - количество рыб, оставшееся тому или иному рыбаку;
take - количество рыб, которые взял тот или иной рыбак;
i - номер рыбака;
partit - величина логического типа, определяющая возможность дележа (взятия каждым рыбаком трети оставшегося количества рыб).
На */школьном алгоритмическом языке /*соответствующая программа имеет вид:
_алг_ Available_partition
_нач_ _цел_ k0, k, take, i, _лог_ partit
¦ _вывод_ _нс_, "Введите количество рыб"
¦ _ввод_ k0
¦ k:=k0
¦ i:=1
¦ _нц_ |цикл “действий” каждого рыбака
¦ ¦ k:=k-1 | осталось после выбрасывания одной рыбы
¦ ¦ _если_ mod(k,n)=0
¦ ¦ ¦_то_ | i-й рыбак может взять треть оставшихся рыб
¦ ¦ ¦ partit:=_да_
¦ ¦ ¦ take:=div(k,3) | берет i-й рыбак
¦ ¦ ¦ k:=k- take | оставшееся количество рыб
¦ ¦ ¦_иначе_
¦ ¦ ¦ partit:=_нет_ | при k0 рыбах дележ невозможен
¦ ¦ _все_
¦ ¦ i:=i+1
¦ _кц___при_ i>n _или_ _не_ partit
¦ _если_ partit
¦ ¦_то_
¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ возможен"
¦ ¦_иначе_
¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ невозможен"
¦ _все_
_кон_
После этого программа нахождения минимального количества рыб, удовлетворяющего условию задачи Дирака, может быть оформлена очень кратко:
_алг_ Задача_Рыбаки_и_рыбки
_нач_ _цел_ k0
¦ k0:=0 |начальное значение диапазона поиска
¦ _нц_ _пока_ _не_ Avail_partit (k0)
¦ ¦ k0:=k0+1 |очередное значение
¦ _кц_
¦ _вывод_ _нс_, "Наименьшее количество рыб,"
¦ _вывод_ "удовлетворяющее условию задачи:", k0
_кон_
где Avail_partit(k0) - вс функция логического типа, определяющая возможность дележа k0/ /рыб в соответствии с условием задачи, составленная на основе программы, приведенной чуть выше:
алг_ _лог_ Avail_partit (_арг_ _цел_ k0)
_нач_ _цел_ k, take, i, _лог_ partit
¦ k:=k0
¦ i:=1
¦ _нц_
¦ ¦ k:=k-1
¦ ¦ _если_ mod(k,3)=0
¦ ¦ ¦_то_
¦ ¦ ¦ partit:=_да_
¦ ¦ ¦ take:=div(k,3)
¦ ¦ ¦ k:=k- take
¦ ¦ ¦ _иначе_
¦ ¦ ¦ partit:=_нет_
¦ ¦ _все_
¦ ¦ i:=i+1
¦ _кц___при_ i>3 _или_ _не_ partit
¦ _знач_:= partit | значение функции
_кон_
Соответствующая программа на Паскале:
{Задача “Рыбаки и рыбки”}
Var
k0: integer;
Function Avail_partit (k0: integer): boolean;
Var
k, take, i: integer;
partit: boolean;
begin
k:=k0;
i:=1;
repeat {цикл “действий” каждого рыбака}
k:=k-1; {осталось после выбрасывания одной рыбы}
if k mod 3 = 0 then
{i-й рыбак может взять треть оставшихся рыб}
begin
partit:=true;
take:=k div 3; {берет i-й рыбак}
k:=k - take {оставшееся количество рыб}
end
else
partit:=false; {дележ невозможен}
i:=i+1
until (i>3) or not partit;
Avail_partit:= partit {значение функции}
end;
BEGIN {Основной программы}
k0:=0; {начальное значение диапазона поиска}
while not Avail_partit(k0) do
k0:=k0+1; {очередное значение}
write('Наименьшее количество рыб, ');
writeln('удовлетворяющее условию задачи: ', k0)
END.
Выполнив программу, можно увидеть, что минимальное количество рыб, удовлетворяющее условию задачи, равно 25. Имеются и большие значения (52, 79, 106, ...).
Имеется и другой решения задачи. Можно, так сказать, идти не от общего количества пойманных рыб, а от числа рыб, доставшихся третьему рыбаку. Если эту величину обозначить take3, то можно записать, что количество рыб, оставшееся тому или иному рыбаку, равно:
1) третьему рыбаку: k3 = 3* take3 + 1;
2) второму: k2 = 3*k3 + 1;
3) первому (то есть общее количество пойманных рыб[2]): k1 = 3*k2 + 1.
Перебирая значения k3, равные 1, 2, 3, …, можно найти такое минимальное число, при котором значения величин k2 и k1 есть целые числа.
Программа, реализующая такой подход к решению задачи, имеет вид:
{Задача "Рыбаки и рыбки"}
Var
take3, k3: word;
k2, k1: real;
BEGIN
take3:=1;
repeat
k3:=3* take3+1;
k2:=k3*3/2+1;
k1:=k2*3/2+1;
take3:= take3+1
until (TRUNC(k2)=k2) and (TRUNC(k1)=k1);
write('Наименьшее количество рыб, ');
writeln('удовлетворяющее условию задачи: ', TRUNC(k1))
END.
Рассмотренную задачу можно решать и при другом числе рыбаков. Соответствующие результаты представлены в таблице (естественно, что некоторые из них являются условными).
Число рыбаков
4
5
6
7
Искомое количество рыб
253
3121
46651
823537
Смотри, для перевода из восьмеричной в десятичную надо это число представить в виде суммы произведения основания восьмеричной системы счисления на соответствующие цифры в разрядах восьмеричного числа:
К примеру, возьмем число 2357, нужно перевести в десятичную, в этом числе 4 цифры и 4 разряда (Разряды считаются, начиная с нулевого которому соответствует младший бит), в соответствии уже с известным правилом представим его в виде суммы степеней с основанием 8:
2357₈ = (2·8³)+(3·8²)+(5·8¹)+(7·8^0) = 2·512 + 3·64 + 5·8 + 7·1 = 1263₁₀
Для вычислений "вручную" и решения примеров и контрольных заданий вам могут пригодиться таблицы степеней оснований изучаемых систем счисления (2, 8, 10, 16)