IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> "Greedy" и монеты.
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Привет.
Вот задача:
В кошельке находятся N монет и их общий вес G:
Каждая монета имеет свою цену и свой вес:
цена: вес:
1 1
5 2
10 3
25 4
50 5
Выяснить минимальную общую стоимость монет которая может находится в кошельке
например:
G=23 N=10
минимальная стоимость =68:
3 монеты по 1
1 монета по 2
и 6 монет по 3
вот мой код:
 
Program P1; Uses Crt;
type Matrice=array[1..3,1..5] of byte;
var A,b:matrice; R,G,N,i,Nb,j,Suma,max,L:integer;
Begin ClrScr;
CheckEof:=True;
a[1,1]:=1; a[1,2]:=5; a[1,3]:=10; a[1,4]:=25; a[1,5]:=50;
a[2,1]:=1; a[2,2]:=2; a[2,3]:=3; a[2,4]:=4; a[2,5]:=5;
writeln('Nr. monet'); readln(N);
writeln('Wes'); readln(G);
if (G div N>5) or (N>G) then exit;
Suma:=0;
for i:=1 to 5 do
if a[2,i]*N>G then begin Nb:=a[2,i]; break; end;
Max:=G div Nb;
R:=G mod Nb;
if R=0 then a[3,Nb]:=Max else begin
i:=1;
if R<N-Max then Max:=Max-1;
a[3,Nb]:=Max;
while (L<N) do begin
L:=0;
if (a[3,i]+a[2,i+1]=G-Nb*max) and (a[3,i]+a[3,Nb]+1=N) then
begin inc(i); a[3,i]:=a[3,i]+1; end else a[3,i]:=a[3,i]+1;
for j:=1 to Nb do
L:=L+a[3,j];
end;
end;
for i:=1 to 3 do begin
for j:=1 to 5 do begin
write(a[i,j],' ');
if i=3 then Suma:=Suma+a[1,j]*a[3,j];
end;
writeln;
end;
writeln(Suma);
readln;
end.

Он рабочий для параметром 10 23, 10 22, и ещё нескольких, и я уверен что есть способ более легкой для это задачи.

Сообщение отредактировано: DarkWishmaster -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ты извини, но в твоем решении я не стал разбираться.. Скажи, какой смысл три разные величины засовывать в один массив? Разве удобно помнить, что у тебя означает строка 2 - вес, цену или количество? Намного удобнее сделать массив записей, например:
coins: array [1..5] of record
w, v, n: integer // вес, значение, количество
end;

Но мне кажется просто три массива тут прекрасно справляются с задачей.
И еще - тебе НАДО поработать над форматированием текста.. Ты вот спрашивал в Свободном про то, какой язык выбрать.. Извини, но ДО ТОГО тебе надо освоить ОБЩИЕ ПРИНЦИПЫ. Код форматировать НАДО. Я уже устал всем это доказывать.. Прийми на веру smile.gif. НАДО.

Вот, я набросал тут два решения. Первое - некрасивое, я его просто так за пять минут сделал, чтоб проверить, какое же на самом деле минимальное решение (то, которое я привел выше, найдено "устно", без программы). В нем намертво зашито 4 цикла - то есть решение годится только для 5 значений монет, и баста. Разбери его, но учти - так программировать НЕ НАДО!! Второе - на основе рекурсии. Этот метод годится для разных наборов монет (достаточно подправить верхние строчки).

Давай, разбирайся и спрашивай, что неясно. Успехов тебе.

Код без рекурсии (как НЕ НАДО) (Показать/Скрыть)

Код с рекурсией (Показать/Скрыть)


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 168
Пол: Мужской

Репутация: -  3  +


Цитата(Lapp @ 25.03.2011 9:26) *

Ты извини, но в твоем решении я не стал разбираться.. Скажи, какой смысл три разные величины засовывать в один массив? Разве удобно помнить, что у тебя означает строка 2 - вес, цену или количество? Намного удобнее сделать массив записей, например:
coins: array [1..5] of record
w, v, n: integer // вес, значение, количество
end;

Но мне кажется просто три массива тут прекрасно справляются с задачей.
И еще - тебе НАДО поработать над форматированием текста.. Ты вот спрашивал в Свободном про то, какой язык выбрать.. Извини, но ДО ТОГО тебе надо освоить ОБЩИЕ ПРИНЦИПЫ. Код форматировать НАДО. Я уже устал всем это доказывать.. Прийми на веру smile.gif. НАДО.

Вот, я набросал тут два решения. Первое - некрасивое, я его просто так за пять минут сделал, чтоб проверить, какое же на самом деле минимальное решение (то, которое я привел выше, найдено "устно", без программы). В нем намертво зашито 4 цикла - то есть решение годится только для 5 значений монет, и баста. Разбери его, но учти - так программировать НЕ НАДО!! Второе - на основе рекурсии. Этот метод годится для разных наборов монет (достаточно подправить верхние строчки).

Давай, разбирайся и спрашивай, что неясно. Успехов тебе.

Код без рекурсии (как НЕ НАДО) (Показать/Скрыть)

Код с рекурсией (Показать/Скрыть)



Спасибо! Буду разбираться.
"Ты вот спрашивал в Свободном про то, какой язык выбрать.. " - ну это я хочу паралельно учить и другой язык, хотя Паскаля и на половину не знаю )
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(DarkWishmaster @ 25.03.2011 11:55) *
хочу паралельно учить и другой язык, хотя Паскаля и на половину не знаю )

Желание что-то делать (в частном случае - учить) всегда похвально. Но второй язык только усилит неразбериху в твоей голове. В результате ты проиграешь на всех фронтах. Решай как можно больше задач на Паскале - это поможет тебе усвоить те самые общие принцмпы, о которых я говорил. После этого раскроешь учебник по другому языку - и тебе покажется, что ты его уже знаешь..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 16.06.2024 4:03
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name