Задача о вероятности, Задача полностью решена Опции

[Zxzc]

Помогите решить задачу:
Мальчик накапливал в копилке деньги. Однажды он увидел в магазине некий товар стоимостью S.
Дело в том что копилка заполнена не до конца, а разбивать ее можно лишь при 100% уверенности,
что количества денег будет достаточно. Но он не помнит сколько монет какого достоинства клал в копилку. Также известна масса пустой копилки и, конечно, текущая масса.
Известны соотношения Номинал <--> Масса монеты. Нужно определить минимальную вероятность и если она равна 100% вывести:"Вперед!!!!!!!!!!!"
Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет.
Проблема в том, что заранее не известно число разновидностей
монет. Также важно, что монеты, номинал которых больше, не всегда тяжелее. Но это не проблема...
Препод предложил идти через двумерный массив(M,N его - большие числа). И каким-то замысловатым способом из 2-х массивов(в первом - номиналы, во втором - массы) получаем массив [m,n]-й элемент к-рого - минимальное кол-во денег... Потом он сам запутался...
Мда.. Давно я так не попадался...

Сообщение отредактировано: Zxzc - 13.05.2006 21:44

[Zxzc]

, рекурсия не причем.
Вот моё, абсолютно не массовое, решение:
Пусть имеются три вида монет массами m1, m2 и m3 и достоинством d1,d2,d3.
MaxAvail - "максимальное число переборов" - найдем по формуле (P/Вес самой дешевой).
P - вес монет, S - стоимость товара.
Тогда все сводится к

For i:=1 to MaxAvail do
 For j:=1 to MaxAvail do
  For k:=1 to MaxAvail do
   If m1*i+m2*j+m3*k = P then
    If d1**i+d2*j+d3*k<S then 
     begin
      Write('Может не хватить!');
       readln;
       exit;       
     end;
Write('Разбивай');
end.

Но это решение не верно т.к.
1. Число разновидностей не известно заранее.
2. Если бы меньшей монете соответствовал меньший вес, то задача решалась бы в 2 строчки:

If P/Massa_min>S/Dostoinstvo_min then Write('Может не хватить!')
Else Write('Разбивай');

Может мы что-то сможем получить, развивая второе рассуждение...

P.S. На дискете у меня есть 2 варианта решения препода. Но вот незадача: "DISK NOT FORMATED. DO YOU WANT FORMAT IT NOW?" Если у меня получится таки достать файлы с исходниками я сразу же их выложу. А иначе до конца выходных...

[volvo]

, рекурсия не причем.

Уверен? Я - нет... Смотри сюда (если твое, "не массовое решение", верно):

const
  max_size = 100; { Работаем до 100 разных номиналов максимум }

type
  arrType = array[1 .. max_size] of integer;

var
  m, d: arrType;
  coin_count, MaxAvail: integer;

  P, s: integer;


procedure check(level: integer; var a: arrType);
var i, j, s_m, s_d: integer;
begin
  if level > coin_count then exit
  else
    if level = coin_count then
      for i := 1 to MaxAvail do begin
        a[level] := i;
        s_m := 0; s_d := 0;
        for j := 1 to level do begin
          s_m := s_m + m[j] * a[j];
          s_d := s_d + d[j] * a[j];
        end;
        if (s_m = P) and (s_d < s) then begin
          writeln('not enough possibly...');
          readln; halt;
        end

        (*
        { Checking }
        for j := 1 to level do
          write(a[j]:4);
        writeln;
        *)

      end

    else
      for i := 1 to MaxAvail do begin
        a[level] := i;
        check(succ(level), a); { Я тебе обещал рекурсию? }
      end;
end;


var
  counters: arrType;

begin
  MaxAvail := 3; { Считай по своей формуле }

  coin_count := 3;
  {
    + заполни массивы m, d нужными значениями,
    и в coin_count занеси КОЛИЧЕСТВО монет
  }

  check(1, counters);
  Writeln('Do it !!!');

end.