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

@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 строчка). Так что спс за помощь!!

Новые блоги и статьи Все статьи Все блоги /
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .

@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