Всем привет! В процессе самообучения языку программирования PHP, я (как, наверняка, и многие другие новички) стараюсь решать задачки, предложенные авторами ресурсов. По своему внутреннему устройству, я не люблю лишний раз дергать людей. Обыкновенно предпочитаю все выискивать сам, до тех пор пока этот поиск дает хотя бы минимальные результаты; на создание этой темы я решался довольно долго. Многие просто пропустили бы это задание и пошли дальше, но мне принципиально интересно понять алгоритм решения. Уверен также, что для многих эта задачка не составила особого труда, но все мы разные и возможно кто-то еще ее не осилил. Погуглив, я понял что задачка эта является типовой для программирования в целом, и отыскав ее решение на другом ЯП, думал что смогу понять алгоритм и записать его синтаксисом PHP. Но не смог. Голова отказалась понимать. Может в школе что недоучил, незнаю.[/size] Вобщем, предлагаю - тем, кому не лень потратить свое драгоценное время на ответ, помогать в этой теме таким "потеряшкам" как я, с пониманием алгоритмов. Итак, к сути. Моим "камнем преткновения", оказалась задачка про банкомат. Необходимо написать алгоритм, который бы выдавал необходимую сумму денег из пула доступных в банкомате купюр, минимально возможным количеством банкнот. При этом не используя "жадный алгоритм", т.е. вычитание наибольшей по номиналу купюры из суммы на выдачу до тех пор, пока это возможно.
и все же жадный алгоритм тут использовать правильнее ) Т.к. чем меньше купюра, тем больше она будет использоваться. Скорее даже выше её незаменимость, т.к. большую купюру в меньшую превратить невозможно.
Неужели так трудно переписать программу с C на PHP? При почти одинаковом синтаксисе? Или вы не понимаете, как организовать ввод купюры? Или вы математику, которую они там расписали, не поняли?
Да. Нет. Видимо да. А самое странное не в том, что я не понял математику, а в том, что я это явно констатировал в первом посте - а Вы не прочитали и задали вопросы.
Посмотрите трансляцию: Код (PHP): $a=Array(10, 50, 100, 500, 1000); // какие виды банкнот есть $k=count($a); // кол-во видов банкнот $n=120; // сумма которую надо выдать // 1 часть алгоритма $INF=PHP_INT_MAX; // const int INF=1000000000; // Значение константы }бесконечность} $F=Array(); // int F[n+1]; $F[0]=0; // F[0]=0; // int m, i; for($m=1; $m<=$n; ++$m) { // for(m=1; m<=n; ++m) // заполняем массив F // m - сумма, которую нужно выдать $F[$m]=$INF; // F[m]=INF; // помечаем, что сумму m выдать нельзя for($i=0; $i<$k; ++$i){ //for(i=0; i<k; ++i) // перебираем все номиналы банкнот if($m>=$a[$i] && $F[$m-$a[$i]]+1<$F[$m]) { // if(m>=a[i] && F[m-a[i]]+1<F[m]) $F[$m] = $F[$m-$a[$i]]+1; // изменяем значение F[m], если нашли } } } // 2 часть алгоритма if($F[$n]==$INF) { // if (F[n]==INF) echo "Требуемую сумму выдать невозможно\r\n"; // cout<<"Требуемую сумму выдать невозможно"<<endl; } else { while($n>0) { // while(n>0) for($i=0;$i<$k;++$i) { // for(i=0;i<k;++i) if ($F[$n-$a[$i]]==$F[$n]-1) { // if (F[n-a[i]]==F[n]-1) echo $a[$i]." "; // cout<<a[i]<<" "; $n-=$a[$i]; // n-=a[i]; break; } } } } Добавлено спустя 5 минут 32 секунды: Помоему алгоритм очень расточительный. Массив $F будет иметь кол-во элементов которому равна сумма для выдачи. Т.е. например 35000 элементов для 35000 руб. Но транслировать конечно проще, чем что-то выдумывать самому)
semnt, спасибо что перевели пример решения в PHP. Но, к сожалению, мой мозг отказывается понимать сам алгоритм. Наверное это бесполезно...и это грустно.
У Вас нету базовых знаний ни по PHP ни по С - поэтому Вы не можете ни транслировать код из С в PHP ни понять готовый код PHP. Начните с учебника по PHP. Когда поймёте основы - пытайтесь писать что-то своё и разбирать чужое. Со временем придёт опыт.
Это не совсем так. Со всеми предыдущими задачами (на построение циклов для вычисления процентов и последующего объединения их в функции, по регулярным выражениям) я справился. И начинаю я именно с базовых знаний, стараюсь ничего не пропускать (отсюда и стремление разобраться в этой задаче). Еще раз спасибо, буду продолжать разбираться
Ну математика там не сложная. Хотя я сам математику не особо люблю, но на то, что описано в статье, меня хватило Они вводят функцию F, которая как раз и показывает минимальное количество банкнот, необходимое для размена какой-то суммы. Поскольку мы номиналы банкнот храним в массиве a, естественно, что . А дальше, если у нас есть сумма n, которую можно разменять, то это делается одним из далее предложенных способов. Т.е. либо вам выдаётся размен суммы (n-a[1]), и прибавляется ещё одна купюра a[1], таким образом количество купюр получается F(n-a[1]) + 1, либо f(n-a[2]) и одна купюра a[2] ну и так далее. Т.е., чтоб посчитать именно минимальное количество банкнот, нужно действительно вычислить минимальный вариант из F(n-a[1]), F(n-a[2]) ну и так далее, и затем прибавить к нему ещё одну банкноту. Реализовано это так в алгоритме: сначала в массив записываются все необходимые значения функции F, а потом они просто перебираются Смутно мне помнится, что в книге Никласа Вирта (автора языка Pascal) я видел более изящное решение такой задачи, без необходимости хранить в массиве столько промежуточных данных
Создате форму с двумя тестовыми полями Метки Число 1 и Число 2 На этой же странице примите данные из формы Проверьте данные на корректность чтобы они были именно числами а не например строками Выведите сумму чисел если полученные значения корректны или сообщение об ошибке если они некорректны примечание для проверки того была ли отправлена форма вам потребуется функция isset <?php if (isset($_POST["calc"])) { function add($x,$y) { return $x + $y; } $n_1 = $_POST["n_1"]; $n_2 = $_POST["n_2"]; //if(isset(is_integer($n_1))) в комментариях момент с которым у меня проблема //$result = add($n_1,$n_2); //elseif(isset(is_integer($n_2))) //$result = add($n_1,$n_2); //else echo "Некорректный ввод "; } ?> <html> <head> <title> Форма</title> </head> <body> <?php if(isset($result)) echo "<p>Вычисление: $result</p>"; ?> <form name="myform" action = "index.php" method = "post"> <p> <input type = "text" name = "n_1" /> <input type = "text" name = "n_2" /> <br /> <input type = "submit" name = "calc" value = "Вычислить" /> </p> </form> </body> </html>
вот чуть переделал но все равно ошибка <?php if (isset($_POST["calc"])) { function add($x,$y) { return $x + $y; } $n_1 = $_POST["n_1"]; $n_2 = $_POST["n_2"]; if((is_integer($n_1))&&(is_integer($n_2))) { $result = add($n_1,$n_2); } else { $result = "Некорректный ввод ";о } ?> <html> <head> <title> Форма</title> </head> <body> <?php if(isset($result)) echo "<p>Вычисление: $result</p>"; ?> <form name="myform" action = "index.php" method = "post"> <p> <input type = "text" name = "n_1" /> <input type = "text" name = "n_2" /> <br /> <input type = "submit" name = "calc" value = "Вычислить" /> </p> </form> </body> </html> is_integer в случае если введенные данные числовые целые выполняет функцию иначе возвращает что данные некорректны