Задачи на цыкл..., обясните мне тупому дураку.... Опции

[Димас]

Общем проблемка такая не могу розобратся в задачках......

наведите меня хоть немного на логику... задачи....

Задача 537

В некоторой стране используются денежные купюры достоинством 1,2,4,8,16,32 и 64. Дано натуральное число n. Как наименьшым количеством таких денежных купюр можно выплатить сумы n,n+1...n+10 ? (Указать количество каждой из используемых для выплаты купюр) Предлогается что имееться достоинство большое количество купбр всех достоинств....


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

обясните как задачу делать ПОЖАЛУЙСТА!!!

З.Ы: мисс_граффити , пардон за тот пост в моей первой теме....

Сообщение отредактировано: Димас - 27.12.2006 2:00

[мисс_граффити]

переводишь n, n+1 ... n+10 в двоичную систему.
допустим, получил
110 - это значит 0 купюр по 1, 1 купюра номиналом 2 и 1 купюра номиналом 4.
единственная проблема может возникнуть, если в числе много цифр... то есть перед разрядом веса 64 стоят еще единички. надо будет посчитать, на сколько они потянут, и выплатить это 64-условноединичными купюрами.

Или решение в лоб: пока сумма больше 64, вычитаешь из нее 64 (считаешь, сколько раз).
После этого: пока сумма больше 32... и т.д.

Сообщение отредактировано: мисс_граффити - 27.12.2006 1:42

[Димас]

Я всё равно не пойму

обясните пожалуйста всё по порядку мне как самому что ни на есть чайнику....

а то я ничего не пойму, незнаю как рещить эту задачу ни в матиматике ни в паскале

[Malice]

Второй вариант:
пока число>64, то {чисел64=чисел64+1, число=число-64 }
если число>32, то {чисел32=1, число=число-32 }
если число>16, то {чисел16=1, число=число-16 }
если число>8, то { чисел8=1, число=число-8 }
если число>4, то { чисел4=1, число=число-4 }
если число>2, то { чисел2=1, число=число-2 }
если число=1, то { чисел1=1}
Сделай так. Но первый вариант красивее и короче, хотя при желании он сворачивается в первый, отличие в порядке вывода купюр..

Сообщение отредактировано: Malice - 27.12.2006 2:28

[Димас]

Ну вроде что то проясняется:-) но с момим умом приходится читать ваши слова по сто раз и вдумыватся по десять раз......

А как это дело на паскале будет выглядеть,напищите плиз кусочок самого цыкла?

[klem4]

пока сумма больше 64, вычитаешь из нее 64

Не проще посмотреть сколько раз число делится нацело на 64, а потом вычесть из числа count64 * 64 ? Ну и так далее ...

[Димас]

Всё написал и решил эту задачку:-)
воть:

 
Program Z537;
uses crt;
var nominal_kupyur:array[1..7] of integer;
    i,suma,kol_kupyur:integer;
begin
     ClrScr;
    {----------------------}
     nominal_kupyur[1]:=  1;
     nominal_kupyur[2]:=  2;
     nominal_kupyur[3]:=  4;
     nominal_kupyur[4]:=  8;
     nominal_kupyur[5]:= 16;
     nominal_kupyur[6]:= 32;
     nominal_kupyur[7]:= 64;
   Textcolor(4);
     writeln('Введите суму ');
     readln(suma);

     {-------------------------------------------------------}
     for i:=High(nominal_kupyur) downto low(nominal_kupyur) do
     begin
         kol_kupyur:=suma div nominal_kupyur[i];
         suma:=suma mod nominal_kupyur[i];
      Textcolor(2);

         if kol_kupyur<>0 then
         writeln('ЄгЇоа ­®¬Ё­ «®¬ ў ',nominal_kupyur[i],' ­г¦­® - ',kol_kupyur,' ивгЄ.');

     end;
     {-------------------------------------------------------}
     writeln;
     write('End');
     readln;
end.

[Malice]

Красиво, но я бы по 1-му варианту пошел, типа:

var s,x:longint;
begin
{readln (x);} X:=64*3+8+4+32; s:=1;
while s<64 do begin
if x and 1=1 then writeln ('1 po ',s);
x:=x shr 1; s:=s*2;
end;
if x>0 then writeln (x,' po ',64);
end.

[klem4]

const
  X: Array [1..7] of Byte = (1, 2, 4, 8, 16, 32, 64);

var
  n, i: Integer;

begin

  write('n = '); readln(n);

  writeln;

  for i := 7 downto 1 do begin

    writeln(X[i], ' : ', n div X[i]);

    n := n - (n div X[i]) * X[i];

  end;
end.
 

Добавлено

Malice мне кажется или твоя прога виснет при X = 65 ?

[Michael_Rybak]

А почему никто не учитывает вот этот кусок:

выплатить сумы n,n+1...n+10

[Malice]

Malice мне кажется или твоя прога виснет при X = 65 ?

Кажется наверное, т.к. там негде..

А почему никто не учитывает вот этот кусок:

А как учесть-то ? Так ?

uses crt;
var n,s,x:longint;
begin
clrscr;
readln (x);
for n:=x to x+10 do begin
x:=n; s:=1; write ('x=',x,'= ');
while s<64 do begin
if x and 1=1 then write (s,',');
x:=x shr 1; s:=s*2;
end;
if x>0 then write (x,'x',64,';');
writeln; end;
end.

[klem4]

Кажется наверное, т.к. там негде..

Ну ты попробовал запустить свою программу с x = 65 ? Я вот щас еще раз попробовал а она еще раз зависла =(((

вот еще вариант:

var
  n, i: LongInt;
  C: Array [0..6] of Integer = (0, 0, 0, 0, 0, 0, 0);

begin
  n := 171;

  for i := 31 downto 0 do
   if ((n shl i) shr 31) = 1 then
    if (31 - i) > 6 then inc(C[6], round(exp((31 - i - 6) * ln(2))))
     else inc(C[31 - i]);

  for i := 0 to 6 do
   writeln(round(exp(i * ln(2))), ' : ', C[i]);
end.

Добавлено:


ГЫ Не удивительно что она виснет, компилятор то перед циклом s обнулил ))) А в цикле s := s * 2 = 0 постоянно ...
))))

[Michael_Rybak]

А как учесть-то ? Так ?

Нет. Я думаю, имелось ввиду объединение множеств.

[Malice]

ГЫ Не удивительно что она виснет, компилятор то перед циклом s обнулил ))) А в цикле s := s * 2 = 0 постоянно ...
))))

Выкинь свой компилятор , т.к. именно перед циклом стоит s:=1;
и такой вариант:
s:=1; while s<64 do s:=s*2; не может повиснуть ни при каких абстоятельствах..
Конечно я сейчас это проверю, (чем черт не шутит), но в 3-х строчках я ошибаюсь _очень_ редко, так сказать, тренирую мозг ручным компилированием

[klem4]

Выкинь свой компилятор , т.к. именно перед циклом стоит s:=1;

Ну компилятор тут точно не причем, видимо я разучился копировать текст из браузера...))

[hiv]

...
    n := n - (n div X[i]) * X[i];
...

Не проще ли эту строу так записать?

n := n mod X[i];