Волшебный мост

@Damir94 · Регистрация: 23.09.2013

Студворк — интернет-сервис помощи студентам

Крестьянин, возвращаясь с ярмарки, увидел на мосту странную картину. Какой-то человек сначала считал деньги в кошельке, затем бросал в реку несколько монеток, бежал на другой конец моста, снова считал деньги в кошельке, и опять бросал несколько монеток и шел на другой конец моста. Наконец, пересчитав свои деньги, он явно обрадовался и отправился в дальнейший путь.
– Что ты делал? Зачем ты бросал деньги в воду? – спросил крестьянин, догнав странного человека.
Видя, что свой секрет скрыть не удастся, человек рассказал, что мост волшебный, что, если бросить с моста ровно 29 копеек, то, как только перейдешь мост, количество рублей в оставшейся сумме денег превращаются в новой сумме в количество копеек, а копейки – в рубли, что, перейдя мост несколько раз, можно получить сумму, намного большую первоначальной.
– Самое важное – вовремя остановиться, – сказал человек и ушёл.
Крестьянин задумался, достал кошелек и пересчитал свои деньги. У него было 46 рублей 47 копеек. «29 копеек – не деньги, дай-ка попробую». После первого прохода у него получилось 18р.46к., после второго прохода – 17р.18к., а после третьего – 89р.16к. «Ух-ты! А еще больше можно получить?» – обрадовался крестьянин. После четвертого прохода у него стало 87р.88к., после пятого – 59р.87к., после шестого – 58р.59к., после седьмого – 30р.58к., после восьмого – 29р.30к., после девятого – 1р.29к., а после десятого осталась 1 копейка.
«Эх, дурачина, надо было после третьего раза остановиться!» – расстроился крестьянин.
Напишите программу, которая по начальной сумме денег у крестьянина определит оптимальное число проходов по мосту для получения наибольшей конечной суммы.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
 
using namespace std;
 
int main()
{
    int count_pass = 0, on_emission = 29, money, max_money, pass;
 
    cout << "Введите произвольную сумму денег: " << endl;
    cin >> money;
 
     do {
 
        count_pass += 1;
        money -= on_emission;
        money = money%100*100 + money/100;
        if(max_money < money) {
            max_money = money;
            pass = count_pass;
        }
 
    } while(money > on_emission);
 
    cout << "____________Ответ_______________" << endl;
    cout << "Максимальная сумма: " << max_money << endl;
    cout << "Номер прохода: " << pass << endl;
    return 0;
}

Добавлено через 1 минуту
Народ помогите разобраться с зацикливанием, добавлял новую переменную и присваивал ей значение и делал проверку на совпадение значение в цикле с условием. Уже не правильно работает программа

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
 
using namespace std;
 
int main()
{
    int count_pass = 0, on_emission = 29, money, max_money, pass;
 
    cout << "Введите произвольную сумму денег: " << endl;
    cin >> money;
    int first_money = money;
     do {
 
        count_pass += 1;
        money -= on_emission;
        money = money%100*100 + money/100;
        if(max_money < money) {
            max_money = money;
            pass = count_pass;
        }
 
    } while(money > on_emission || first_money != money);
 
    cout << "____________Ответ_______________" << endl;
    cout << "Максимальная сумма: " << max_money << endl;
    cout << "Номер прохода: " << pass << endl;
    return 0;
}

@Fyret · 23.09.2013, 16:42

Первый вариант правильный (я бы только сделал цикл с предусловием). С одной стороны, на некоторых исходных данных этот цикл становится бесконечным. С другой стороны, из условия задачи ясно, что этот жлобский мост никогда не даст больше, чем 9999 копеек. Т.е. за 9999 итераций можно перебрать все возможные суммы с точностью до копейки. Вот этим и надо ограничить цикл.

P.S. Эксперименты показывают, что на самом деле различных сумм не более 198, но как это обосновать математически - не представляю.

@Damir94 · 23.09.2013, 16:51 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
 
using namespace std;
 
int main()
{
    int count_pass = 0, on_emission = 29, money, max_money, pass;
 
    cout << "Введите произвольную сумму денег: " << endl;
    cin >> money;
 
     while(money > on_emission) {
 
        count_pass += 1;
        money -= on_emission;
        money = money%100*100 + money/100;
 
        if(max_money < money) {
            max_money = money;
            pass = count_pass;
        }
 
    }
 
    cout << "____________Ответ_______________" << endl;
    cout << "Максимальная сумма: " << max_money << endl;
    cout << "Номер прохода: " << pass << endl;
    return 0;
}

Да я делал так, ставил условие внутри цикла на 10000 итераций и потом выходил из него. Но преподаватель у меня упрямый, говорит что нужно в самом условии цикла прописать чтобы он выходил из зацикливания

@Fyret · 23.09.2013, 16:53

Сообщение от Damir94

в самом условии цикла прописать чтобы он выходил из зацикливания

C++
1
while(money > on_emission && count_pass < 10000)

не?

@Damir94 · 23.09.2013, 17:09 **[ТС]**

Если бы так можно было

(. Зацикливание же происходит из-за повторения введенной суммы, вот надо в условии цикла задать условие чтобы они не повторялись.

Добавлено через 5 минут

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
using namespace std;
 
int main()
{
    int count_pass = 0, on_emission = 29, money, max_money = 0, pass = 0;
 
    cout << "Введите произвольную сумму денег: " << endl;
    cin >> money;
    int first_money = money;
    do {
        count_pass += 1;
        money -= on_emission;
        money = money%100*100 + money/100;
        if(max_money < money) {
            max_money = money;
            pass = count_pass;
        }
    } while(money > on_emission && first_money != money);
 
    cout << "____________Ответ_______________" << endl;
    cout << "Максимальная сумма: " << max_money << endl;
    cout << "Номер прохода: " << pass << endl;
    return 0;
}

Это просто тупость, до этого такой же код писал не работало. Сейчас переписал, все заработало. Ладно спс за помощь. Пользуйтесь!))

@Fyret · 23.09.2013, 17:13

Сообщение от Damir94

Это просто тупость, до этого такой же код писал не работало. Сейчас переписал, все заработало.

Потому что не такой же :-)

А если изначальная сумма 100 р. 20.к ? Ваш код работать не будет, да и вообще я не уверен, что всякая исходная сумма попадет в цикл. Предлагаю такой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <map>
 
int main()
{
    int count_pass = 0, on_emission = 29, money, max_money = 0, pass;
    
    std::map< int, int > variants = std::map< int, int >();
 
    std::cout << "Initial money: ";
    std::cin >> money;
 
    do
    {
        variants[ money ] = count_pass++;
 
        money -= on_emission;
        money = money%100*100 + money/100;
    }
    while( money > on_emission && !variants.count( money ) );
 
    std::cout << "Max money: " << variants.rbegin()->first << std::endl;
    std::cout << "Pass: " << variants.rbegin()->second << std::endl;
    
    return 0;
}

@Damir94 · 23.09.2013, 17:19 **[ТС]**

Контрольные примеры:
7699–9904–81
1136–9902–63
3563–8916–10
6287–6287–0
7069–9998–196
3599–9964–197
7038–9967–196

Вот исходные примеры, по ним сверил, все выводит правильно. А на остальное уж не важно) Я другой язык программирования узучаю, а это для универа на автомат надо сделать. И есть не понятный код(например 8 строчка). Так что спс за помощь!!

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@Fyret 249 / 219 / 63 Регистрация: 30.07.2013 Сообщений: 465
	23.09.2013, 16:42
	Первый вариант правильный (я бы только сделал цикл с предусловием). С одной стороны, на некоторых исходных данных этот цикл становится бесконечным. С другой стороны, из условия задачи ясно, что этот жлобский мост никогда не даст больше, чем 9999 копеек. Т.е. за 9999 итераций можно перебрать все возможные суммы с точностью до копейки. Вот этим и надо ограничить цикл. P.S. Эксперименты показывают, что на самом деле различных сумм не более 198, но как это обосновать математически - не представляю. 1

@Damir94 0 / 0 / 3 Регистрация: 23.09.2013 Сообщений: 29
	23.09.2013, 17:19 [ТС]
	Контрольные примеры: 7699–9904–81 1136–9902–63 3563–8916–10 6287–6287–0 7069–9998–196 3599–9964–197 7038–9967–196 Вот исходные примеры, по ним сверил, все выводит правильно. А на остальное уж не важно) Я другой язык программирования узучаю, а это для универа на автомат надо сделать. И есть не понятный код(например 8 строчка). Так что спс за помощь!! 0