Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > PHP
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.07.2017, 11:45   #1
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию Задача «Разменный автомат»

Задача «Разменный автомат», с условием ,что у автомата конечное число каждой купюры которые хранятся в файле, а также добавить учет выданных средств. Почему-то выводит всегда одни нули и не отнимает значение в файлах, функции проверял, по отдельности работают нормально. Спасибо за помощь:
Код:
<?php 
// Задача «Разменный автомат», с условием ,что у автомата
// конечное число каждой купюры которые хранятся в файле, а
// также добавить учет выданных средств
// $n - сумма для размена
$n = 1779;
foreach (avtoMoney($n) as $key => $value) {
    echo "$key = $value <br>";
}
 
function avtoMoney($n){
    $path = "money/";
// Массив сех значений купюр
    $money = array('1' => 1, '2' => 2, '5' => 5, '10' => 10, '20' => 20,
        '50' => 50, '100' => 100, '200' => 200, '500' => 500);
// Массив для учета количества выданных купюр
    $countMoney = array('1' => 0, '2' => 0, '5' => 0, '10' => 0, '20' => 0,
        '50' => 0, '100' => 0, '200' => 0, '500' => 0);
 
    foreach ($money as $key => $value) {
        // Если делится целочисленным делением и есть купюры
        if ((integer)($n/$value) && (checkFiles($path . $key . ".txt"))) {
            $n = $n % $value;
            // Добавляю +1 в выданную купюру
            foreach ($countMoney as $key2 => $value2) {
                $value2++;
            }
 
        }
    }
    return $countMoney;
}
 
function checkFiles($path){
    // Получаю данные с файла
    $string = file_get_contents($path);
    if ($string > 0) {
        // -1 купюра
        $string--;
        // Перезаписываю новое значение
        $file = fopen($path, "r+");
        fputs($file, $string);
        fclose($file);
        return true;
    }
    return false;
}
?>
Max00766 вне форума Ответить с цитированием
Старый 24.07.2017, 11:52   #2
Andkorol
Старожил
 
Регистрация: 31.05.2010
Сообщений: 3,301
По умолчанию

Где текстовые файлы, какие значения в них записаны?
Andkorol вне форума Ответить с цитированием
Старый 24.07.2017, 12:50   #3
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от Andkorol Посмотреть сообщение
Где текстовые файлы, какие значения в них записаны?
Извините, забыл
Текстовые файлы вида: 500.txt, 200.txt, 100.txt. 50.txt и так далее, в папке money, в них записаны рандомные числа которые обозначают количество купюр
test.com.zip
Max00766 вне форума Ответить с цитированием
Старый 24.07.2017, 16:52   #4
Andkorol
Старожил
 
Регистрация: 31.05.2010
Сообщений: 3,301
По умолчанию

После первой же итерации цикла в avtoMoney() значение атрибута, переданного в эту функцию, становится равным 0 – потому, что остаток от деления 1779 на 1 = 0 ($n = $n % $value;).
И все дальнейшие действия не имеют смысла – т.к. теперь $n = 0;

// Добавляю +1 в выданную купюру – это вообще не работает, и цикл там не нужен – т.к. речь идёт о купюре только одного конкретного номинала.
Должно быть примерно так:
$countMoney[$key] = ++$countMoney[$key];

Дальше не проверял – но общая логика работы с купюрами явно неверная.
Размен монет – это довольно популярный пример задачи по жадным алгоритмам, рекомендую погуглить и изучить.
Andkorol вне форума Ответить с цитированием
Старый 24.07.2017, 18:02   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

полностью согласен.
задачка не простая.

для затравки:
Код:
function avtoMoney($n){
	$path = "money/";
	$money = array(1, 2, 5, 10, 20, 50, 100, 200, 500);

	$MoneyInAuto=array();
	$all_sum_in_bank=0;
	foreach ($money as $val) {
            $f=fopen($path . $val . ".txt","r");
	    $s=fread($f, 2);
	    $MoneyInAuto[$val]=$s;
	    $all_sum_in_bank += $val * (int)$s;
	    fclose($f);
	    echo $val . ": ".$s." шт.<br>\n";

        }

	// заполняем жадным алгоритмом
	$countMoney=array();
	$sum=$n;
	if($sum>$all_sum_in_bank)
		echo "денег в банкомате меньше, чем заданная сумма!<br>";
	for($i=count($money)-1;($i>=0 && $sum!=0);$i--){
		$curren_value=$money[$i];
		if($sum>=$curren_value){
			$k= (int) ($sum / $curren_value);
			$nq=min($k, $MoneyInAuto[$curren_value]);
			echo " summa = $sum купюра значением $curren_value рублей. Выдать можно $nq купюр. ";
			$sum = $sum - $nq * $curren_value;
			echo " остаток суммы = $sum<br>\n";
			if($nq>0)
				$countMoney[$curren_value]=$nq;
		}
	}

	// если $sum не равна нулю - выдать сумму "жадным алгоритмом" НЕ ПОЛУЧИЛОСЬ!
       // нужно перебирать другие варианты
       return  $countMoney;
}
собственно, проблема в том, что жадный алгоритм при ограниченном числе купюр не всегда находит существующее решение.
поэтому, если он не нашел решение, это не означает, что его нет. Нужно пытаться решить другим способом (например, перебором).

если интересно, могу написать случай, когда жадный алгоритм не даёт решения, хотя оно есть.

Последний раз редактировалось Serge_Bliznykov; 24.07.2017 в 18:41.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.07.2017, 18:39   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Если, например, нужно выдать 11, а купюры по 5 и 2, то жадный алгоритм не сможет. Скорее динамическое программирование
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 24.07.2017, 18:45   #7
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Размен монет - это задача о рюкзаке. Жадным алгоритмом в общем случае НЕ берётся. Стандартный подход - динамическое программирование по набираемой сумме
Black Fregat вне форума Ответить с цитированием
Старый 24.07.2017, 18:56   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Размен монет - это задача о рюкзаке.
ну, это не совсем рюкзак, там как бы задача другая - максимизация стоимости взятых вещей.
Но, по сути, согласен.


Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Жадным алгоритмом в общем случае НЕ берётся.
и с этим согласен.
Хотя, уверен, что в реальных банкоматах именно жадный алгоритм и используется
или есть набор купюр или он просто отказывается выдать нужную сумму.
Да и, справедливости ради, жадный алгоритм покроет 99% требуемых сумм.

Но, конечно, это не решение задачи.


Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Стандартный подход - динамическое программирование по набираемой сумме
а можно ссылку на решение/алгоритм?
ну или, если не сложно, распишите, пожалуйста, как строится реккурентная динамика в этом конкретном случае.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.07.2017, 19:05   #9
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

https://informatics.mccme.ru/mod/book/view.php?id=815
Мельком глянул не вникая ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 24.07.2017, 20:41   #10
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
полностью согласен.
задачка не простая.

для затравки:
Код:
function avtoMoney($n){
	$path = "money/";
	$money = array(1, 2, 5, 10, 20, 50, 100, 200, 500);

	$MoneyInAuto=array();
	$all_sum_in_bank=0;
	foreach ($money as $val) {
            $f=fopen($path . $val . ".txt","r");
	    $s=fread($f, 2);
	    $MoneyInAuto[$val]=$s;
	    $all_sum_in_bank += $val * (int)$s;
	    fclose($f);
	    echo $val . ": ".$s." шт.<br>\n";

        }

	// заполняем жадным алгоритмом
	$countMoney=array();
	$sum=$n;
	if($sum>$all_sum_in_bank)
		echo "денег в банкомате меньше, чем заданная сумма!<br>";
	for($i=count($money)-1;($i>=0 && $sum!=0);$i--){
		$curren_value=$money[$i];
		if($sum>=$curren_value){
			$k= (int) ($sum / $curren_value);
			$nq=min($k, $MoneyInAuto[$curren_value]);
			echo " summa = $sum купюра значением $curren_value рублей. Выдать можно $nq купюр. ";
			$sum = $sum - $nq * $curren_value;
			echo " остаток суммы = $sum<br>\n";
			if($nq>0)
				$countMoney[$curren_value]=$nq;
		}
	}

	// если $sum не равна нулю - выдать сумму "жадным алгоритмом" НЕ ПОЛУЧИЛОСЬ!
       // нужно перебирать другие варианты
       return  $countMoney;
}
собственно, проблема в том, что жадный алгоритм при ограниченном числе купюр не всегда находит существующее решение.
поэтому, если он не нашел решение, это не означает, что его нет. Нужно пытаться решить другим способом (например, перебором).

если интересно, могу написать случай, когда жадный алгоритм не даёт решения, хотя оно есть.
Спасибо, помогло)
Max00766 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
конечный автомат fkty Помощь студентам 18 17.01.2015 18:49
автомат crechet51 Microsoft Office Excel 8 08.10.2012 02:04
автомат crechet51 Помощь студентам 0 07.10.2012 01:50
Клеточный автомат Munya Фриланс 4 08.05.2010 13:34
Клеточный автомат Noor Помощь студентам 4 29.11.2007 09:19