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

AAOO AAOO    3   29.09.2019 03:01    1

Ответы
Саша73838 Саша73838  09.10.2020 01:51

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

ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика