Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Damir94
0 / 0 / 3
Регистрация: 23.09.2013
Сообщений: 29
23.09.2013, 16:10     Волшебный мост #1
Крестьянин, возвращаясь с ярмарки, увидел на мосту странную картину. Какой-то человек сначала считал деньги в кошельке, затем бросал в реку несколько монеток, бежал на другой конец моста, снова считал деньги в кошельке, и опять бросал несколько монеток и шел на другой конец моста. Наконец, пересчитав свои деньги, он явно обрадовался и отправился в дальнейший путь.
– Что ты делал? Зачем ты бросал деньги в воду? – спросил крестьянин, догнав странного человека.
Видя, что свой секрет скрыть не удастся, человек рассказал, что мост волшебный, что, если бросить с моста ровно 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
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
23.09.2013, 16:42     Волшебный мост #2
Первый вариант правильный (я бы только сделал цикл с предусловием). С одной стороны, на некоторых исходных данных этот цикл становится бесконечным. С другой стороны, из условия задачи ясно, что этот жлобский мост никогда не даст больше, чем 9999 копеек. Т.е. за 9999 итераций можно перебрать все возможные суммы с точностью до копейки. Вот этим и надо ограничить цикл.

P.S. Эксперименты показывают, что на самом деле различных сумм не более 198, но как это обосновать математически - не представляю.
Damir94
0 / 0 / 3
Регистрация: 23.09.2013
Сообщений: 29
23.09.2013, 16:51  [ТС]     Волшебный мост #3
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
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
23.09.2013, 16:53     Волшебный мост #4
Цитата Сообщение от Damir94 Посмотреть сообщение
в самом условии цикла прописать чтобы он выходил из зацикливания
C++
1
while(money > on_emission && count_pass < 10000)
не?
Damir94
0 / 0 / 3
Регистрация: 23.09.2013
Сообщений: 29
23.09.2013, 17:09  [ТС]     Волшебный мост #5
Если бы так можно было (. Зацикливание же происходит из-за повторения введенной суммы, вот надо в условии цикла задать условие чтобы они не повторялись.

Добавлено через 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
184 / 170 / 13
Регистрация: 30.07.2013
Сообщений: 359
23.09.2013, 17:13     Волшебный мост #6
Цитата Сообщение от 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.09.2013, 17:19     Волшебный мост
Еще ссылки по теме:

Turbo Pascal Задача волшебный треугольник
Волшебный нелокальный принтер
Python Задача "Волшебный мост"

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Damir94
0 / 0 / 3
Регистрация: 23.09.2013
Сообщений: 29
23.09.2013, 17:19  [ТС]     Волшебный мост #7
Контрольные примеры:
7699–9904–81
1136–9902–63
3563–8916–10
6287–6287–0
7069–9998–196
3599–9964–197
7038–9967–196

Вот исходные примеры, по ним сверил, все выводит правильно. А на остальное уж не важно) Я другой язык программирования узучаю, а это для универа на автомат надо сделать. И есть не понятный код(например 8 строчка). Так что спс за помощь!!
Yandex
Объявления
23.09.2013, 17:19     Волшебный мост
Ответ Создать тему
Опции темы

Текущее время: 02:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru