Рассмотрим пример решения задачи:
<span>Однажды Винни-Пух захотел полакомиться медом и пошел к пчелам в гости. По дороге нарвал букет цветов, чтобы подарить труженицам пчелкам. Пчелки очень обрадовались, увидев мишку с букетом цветов, и сказали: «У нас есть большая бочка с медом. Мы дадим тебе меда, если ты сможешь с помощью двух сосудов вместимостью 3 л и 5 л налить себе 4 л!» Винни-Пух долго думал, но все-таки смог решить задачку. Как он это сделал?
</span>
<span><span><u>Решение:</u>
<span>Как в результате можно получить 4 л? Нужно из 5-литрового сосуда отлить 1 л. А как это сделать? Нужно в 3-литровом сосуде иметь ровно 2 л. Как их получить? – Из 5-литрового сосуда отлить 3 л.
Решение лучше и удобнее оформить в виде таблицы:</span></span>
<span><span>Ходы123456</span><span>5 л522-54</span><span>3 л-3-223</span></span>
</span>
<span>Наполняем из бочки 5-литровый сосуд медом (1 шаг). Из 5-литрового сосуда отливаем 3 л в 3-литровый сосуд (2 шаг). Теперь в 5-литровом сосуде осталось 2 литра меда. Выливаем из 3-литрового сосуда мед назад в бочку (3 шаг). Теперь из 5-литрового сосуда выливаем те 2 литра меда в 3-литровый сосуд (4 шаг). Наполняем из бочки 5-литровый сосуд медом (5 шаг). И из 5-литрового сосуда дополняем медом 3-литровый сосуд. Получаем 4 литра меда в 5-литровом сосуде (6 шаг). Задача решена.
Поиск решения можно было начать с такого действия: к трем литрам добавить 1 литр.</span> <span>Но тогда решение будет выглядеть следующим образом:
<span><span>Ходы12345678</span><span>5 л-335-114</span><span>3 л3-311-3<span>-( по этому примеру реши)
<span>
</span></span></span></span></span>
#!/usr/bin/env python
# coding: utf-8
"""Определение типа треугольника по сторонам.
Python 2.X.
"""
msg = 'Введите стороны треугольника: '
input = raw_input(msg).split()
try:
a, b, c = [float(i) for i in input]
except ValueError:
print('Введены не числовые значения! Выход...')
quit()
if (a >= b + c or
b >= a + c or
c >= a + b):
print('Не', end=' ')
elif a ** 2 + b ** 2 == c ** 2:
print('Прямоугольный', end=' ')
elif (a ** 2 + b ** 2 > c ** 2 and
a ** 2 + c ** 2 > b ** 2 and
c ** 2 + b ** 2 > a ** 2):
print('Остроугольный', end=' ')
else:
print('Тупоугольный', end=' ')
print('треугольник')
Такой вариант на простом паскале со стратегией жадность
var
n, s, i: integer;
x: array[1..100]of integer;
answer: string;
begin
readln(n);
for i := 1 to n do
read(x[i]);
readln(s);
answer := IntToStr(s) + ' = ';
for i := n downto 1 do
begin
answer := answer + IntToStr(s div x[i]) + '*' + IntToStr(x[i]);
s := s mod x[i];
if i > 1 then
answer := answer + ' + ';
end;
if s <> 0 then
writeln('NO')
else
writeln(answer);
end.
Более полный и правильный вариант решения, но и куда более сложный
//PascalABC.Net 3.1 сборка 1200
uses System.Collections.Generic;
uses System;
var
x := new List<integer>;
c := new List<Tuple<string, integer>>;
procedure getParcelling(sum, step: integer; coefficients: string; count: integer);
begin
if step >= x.Count then begin
if sum = 0 then c.Add((coefficients, count));
Exit;
end;
if step < 0 then step := 0;
for var j := 0 to (sum div x[step]) do
begin
var s := '';
if j > 0 then begin
if step > 0 then s += ' + ';
s += IntToStr(j) + '*' + IntToStr(x[step]);
end;
getParcelling(sum - x[step] * j, step + 1, coefficients + s, count + j);
end;
end;
begin
x := ReadArrInteger('x:', ReadInteger('n =')).ToList;
var sum := ReadInteger('sum =');
getParcelling(sum, 0, '', 0);
if c.Count = 0 then
writeln('No')
else begin
var min := c.Min(cc -> cc.Item2);
Println(c.Where(cc -> cc.Item2 = min));
end;
end.
