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

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 2744, средняя оценка - 4.89
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
#1

Задачи для тренировки и лучшего понимания - C++

15.07.2010, 05:53. Просмотров 338448. Ответов 1272
Метки нет (Все метки)

Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:
Лучшие ответы (59)
Сообщение: #857841 Сообщение: #857861 Сообщение: #858352 Сообщение: #859371 Сообщение: #860160 Сообщение: #860255 Сообщение: #860259 Сообщение: #860317 Сообщение: #860368 Сообщение: #860466 Сообщение: #860508 Сообщение: #860720 Сообщение: #861091 Сообщение: #862174 Сообщение: #862617 Сообщение: #867259 Сообщение: #870298 Сообщение: #872053 Сообщение: #876456 Сообщение: #880114 Сообщение: #882889 Сообщение: #884418 Сообщение: #886414 Сообщение: #886989 Сообщение: #887733 Сообщение: #888464 Сообщение: #888487 Сообщение: #888941 Сообщение: #888947 Сообщение: #889040 Сообщение: #889450 Сообщение: #889587 Сообщение: #891772 Сообщение: #891790 Сообщение: #891862 Сообщение: #897758 Сообщение: #897782 Сообщение: #906325 Сообщение: #907991 Сообщение: #943672 Сообщение: #943700 Сообщение: #967735 Сообщение: #1053777 Сообщение: #1054209 Сообщение: #1083853 Сообщение: #1083928 Сообщение: #1131058 Сообщение: #1131359 Сообщение: #1273743 Сообщение: #1275465 Сообщение: #1276743 Сообщение: #1279215 Сообщение: #1282583 Сообщение: #1309088 Сообщение: #1315633 Сообщение: #1366395 Сообщение: #1550164 Сообщение: #1603678 Сообщение: #1604364
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2010, 05:53     Задачи для тренировки и лучшего понимания
Посмотрите здесь:

C++ Какой компилятор выбрать для лучшего изучения С++ по книге Берна Страуструпа?п
C++ Элементарные программы, для лучшего понимания языка...
Нужны задачи для тренировки C++
C++ Киньте задачки для тренировки
C++ Нужны простые задачи для тренировки
Нужны задачи для тренировки C++
На соревнованиях по фигурному катанию оценки заносятся в компьютер. Составить программу для вывода на экран лучшего результата после каждого выступлен C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
5764 / 3413 / 255
Регистрация: 08.02.2010
Сообщений: 7,430
28.07.2010, 08:07     Задачи для тренировки и лучшего понимания #241
GаlаX, 3 > 1, значит, нельзя
Можно ложить 1 на 2 и на 3, 2 на 3
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 08:20     Задачи для тренировки и лучшего понимания #242
Цитата Сообщение от Aye Aye Посмотреть сообщение
Каждое перекладывание должно производиться через средний колышек
то есть в каждом ходе участвует средный колышек?
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
28.07.2010, 09:38     Задачи для тренировки и лучшего понимания #243
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
////////////////////////////////////////////////////////////////////////////////////////////
//Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков 
//с левого колышка A на правый колышек C, если прямой обмен дисками между A и C запрещен. 
//(Каждое перекладывание должно производиться через средний колышек B. 
//Больший диск нельзя класть на меньший.)
////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
 
 
typedef std::string  T_str;
 
T_str  get_Hanoi_tower_solution
    (
        int n, 
        char A, 
        char B,
        char C
    )
{    
    if(n == 1)
    {
        return T_str(1, A) + C + ' ';
    }
    else
    {
        return  get_Hanoi_tower_solution(n - 1, A, C, B) 
                + T_str(1, A) + C + ' '
                + get_Hanoi_tower_solution(n - 1, B, A, C);
    }
    
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите высоту башни: ";
    int n;
    std::cin >> n;
    std::cout << "Решение: "
              << std::endl;
    std::cout << get_Hanoi_tower_solution(n, 'A', 'B', 'C')
              << std::endl;   
    return 0;
}
Добавлено через 13 минут
Вообще-то вот так красивше будет:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
////////////////////////////////////////////////////////////////////////////////////////////
//Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков 
//с левого колышка A на правый колышек C, если прямой обмен дисками между A и C запрещен. 
//(Каждое перекладывание должно производиться через средний колышек B. 
//Больший диск нельзя класть на меньший.)
////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
 
 
typedef std::string  T_str;
 
T_str  get_Hanoi_tower_solution
    (
        int n, 
        char A, 
        char B,
        char C
    )
{    
    if(n == 0)
    {
        return "";
    }
    else
    {
        return  get_Hanoi_tower_solution(n - 1, A, C, B) 
                + T_str(1, A) + C + ' '
                + get_Hanoi_tower_solution(n - 1, B, A, C);
    }
    
}
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите высоту башни: ";
    int n;
    std::cin >> n;
    std::cout << "Решение: "
              << std::endl;
    std::cout << get_Hanoi_tower_solution(n, 'A', 'B', 'C')
              << std::endl;   
    return 0;
}
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 13:27     Задачи для тренировки и лучшего понимания #244
Итак. Давайте я пока выложу
Mr.X, это всё хорошо, но вы перекладыаете "кружки" непосредственно с A на С и с С на А, что запрещенно по условию задачки.
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 13:59     Задачи для тренировки и лучшего понимания #245
Вот мат. часть задачки.
Цитата Сообщение от Aye Aye Посмотреть сообщение
привести математические обоснования
На данный момент я займусь изложением придуманной теории: как найти мин. количество ходов. Сначала я просто попробовал подсчитать, сколько нужно ходов для разных n. Вот что у меня получилось (n кол. "кружочков", k кол. ходов):
Код
n=1, k=2;
n=2, k=8;
n=3, k=26;
n=4, k=80;
По моему этого достаточно что бы заметить что новый k выражается по формуле 3(предыдущий k)+2. А теперь то что я "заметил", надо доказать. Итак. Допусти мы знаем, что для некого кол. "кружочков" n, есть мин. кол. ходов k. Каким оно будет для n+1? Начнем рассуждать. Что бы перенести (n+1)-ый кружочек с палочки А на палочку С, мы должны "преодолеть" палочку В. Для этого, мы должны перенести все остальные кружочки на палочку С, МИНИМАЛЬНЫМ количеством ходов. А оно (по условию) k. Итак, теперь мы знаем, что для n+1 кружочков, мин. кол. ходов для (n+1) кружочков будет k+... (дальше узнаем, чему равны эти "..."). Что мы имеем? Пирамидку из n кружочков на палочке С и (n+1)-ый кружочек на палочке А. Переносим его на палочку В. Теперь кол. мин. ходов для (n+1) кружочков = k+1+... . Далее, мы должны перенести (n+1)-ый кружочек на палочку С, для чего должны сначала освободить ее. Переносим пирамидку из n кружочков на палочку А, МИНИМАЛЬНЫМ кол. ходов. Мы знаем что оно = k. Теперь мин. кол. ходов для (n+1) кружочков = k+1+k... . Теперь, когда палочка С свободна, переносим на нее (n+1)-ный кружочек. Это уже k+1+k+1 ходов. А теперь перенесем пирамидку с А на С, где лежит наш (n+1)-ный кружок. А это уже k+1+k+1+k= 3k+2. А реализовать это рекурсией не сложно. Чем я сейчас и займусь...
Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.07.2010, 14:02     Задачи для тренировки и лучшего понимания #246
nikkka, да колышек B будет участвовать в каждом ходу.

Mr.X, к сожалению не правильно, nikkka все верно вроде бы.
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 14:04     Задачи для тренировки и лучшего понимания #247
Aye Aye, а рассуждения хоть правельные? :S
Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
28.07.2010, 14:12     Задачи для тренировки и лучшего понимания #248
nikkka, я немного запутался в твоем обосновании )) вроде верно, сама идея по крайней мере верна, совет небольшой: надо написать формулу, а потом писать программу.
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 14:29     Задачи для тренировки и лучшего понимания #249
Aye Aye, ну знаешь...
это теория. надо ДОКАЗАТЬ что Ваш алгоритм правелен, и что это ЕДИНСТВЕННЫЙ кратчайший путь. Это я и сделал. А саму программу я дописываю. Скоро скину.

Добавлено через 13 минут
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
30
31
32
33
34
35
36
#include <iostream>
#include <string.h>
#include <conio.h>
using namespace std;
string inverse(string s1)
{
    string s2=s1;
    int i=0;
    int size=0;
    while(s1[i]!='\0')
    {
        size++;
        i++;
    }
    i=0;
    while(s1[i]!='\0')
    {
        s2[i]=s1[size-i-1];
        i++;
    }
    return s2;
}
string theway(int n)
{
    string s1;
    if(n==1) s1="AB BC";
    if(n==2) s1="AB BC AB CB BA BC AB BC";
    if(n>2) s1=theway(n-1)+" AB "+inverse(theway(n-1))+" BC "+theway(n-1);
    return s1;
}
int main()
{
    cout<<theway(3);
    getch();
    return 0;
}
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
28.07.2010, 14:39  [ТС]     Задачи для тренировки и лучшего понимания #250
nikkka, Красота! А я так и не додумался как сие сделать.
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 14:59     Задачи для тренировки и лучшего понимания #251
Ещё задач!!!!!...
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
28.07.2010, 15:05     Задачи для тренировки и лучшего понимания #252
nikkka, порешай тимус
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 15:22     Задачи для тренировки и лучшего понимания #253
Хохол, извените, что порешать? : O
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
28.07.2010, 15:29     Задачи для тренировки и лучшего понимания #254
acm.timus.ru
Вот выбрал легкую и прикольную задачу (только не залезай в обсуждение - сразу решение узнаешь)
http://acm.timus.ru/problem.aspx?space=1&num=1082
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 15:36     Задачи для тренировки и лучшего понимания #255
Хохол, прочитал, но преревод дебильный... задачу понять не смог.

Не по теме:

зачем переводить задачки на англ.????

Nameless One
Эксперт С++
5764 / 3413 / 255
Регистрация: 08.02.2010
Сообщений: 7,430
28.07.2010, 15:47     Задачи для тренировки и лучшего понимания #256
nikkka, там в левом верхнем углу можно язык переключить
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 15:49     Задачи для тренировки и лучшего понимания #257
Nameless One, а, ну да...
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
28.07.2010, 19:15     Задачи для тренировки и лучшего понимания #258
Цитата Сообщение от nikkka Посмотреть сообщение
Итак. Давайте я пока выложу
Mr.X, это всё хорошо, но вы перекладыаете "кружки" непосредственно с A на С и с С на А, что запрещенно по условию задачки.
А, да, что-то я условия не дочитал. Тогда уж так полаконичнее:
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
30
31
32
33
34
35
36
37
38
39
////////////////////////////////////////////////////////////////////////////////////////////
//Найдите кратчайшую последовательность перекладываний, перемещающих башню из n дисков 
//с левого колышка A на правый колышек C, если прямой обмен дисками между A и C запрещен. 
//(Каждое перекладывание должно производиться через средний колышек B. 
//Больший диск нельзя класть на меньший.)
////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <algorithm>
////////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
////////////////////////////////////////////////////////////////////////////////////////////
T_str  get_tower_solution(int n)
{    
    if(n == 0)
    {
        return "";
    }
    else
    {
        T_str  sol_str = get_tower_solution(n - 1);
        T_str  sol_str_rev(sol_str);
        std::reverse_copy(sol_str.begin(), sol_str.end(), sol_str_rev.begin());
        return  sol_str + " AB " + sol_str_rev + " BC " + sol_str;                
    }    
}
////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите высоту башни: ";
    int n;
    std::cin >> n;
    std::cout << "Решение: "
              << std::endl;
    std::cout << get_tower_solution(n)
              << std::endl;   
    return 0;
}
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
28.07.2010, 20:37     Задачи для тренировки и лучшего понимания #259
Mr.X, есть функция котороя инверсирует строку?????
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2010, 21:18     Задачи для тренировки и лучшего понимания
Еще ссылки по теме:

C++ Какая база требуется для понимания C++?
C++ Нужен пример рекурсивной функции для понимания ее назначения и практической пользы
C++ Builder Прошу примеров для понимания INDY
Книги для тренировки/развития котелка и просто убийства времени C++
Дайте задания для тренировки C++

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

Или воспользуйтесь поиском по форуму:
MikeSoft
Эксперт C++
3789 / 1771 / 85
Регистрация: 21.11.2009
Сообщений: 2,540
28.07.2010, 21:18     Задачи для тренировки и лучшего понимания #260
nikkka, это глобальный вопрос? или по конкретной задаче?
Для реверса строки есть функция strrev
Yandex
Объявления
28.07.2010, 21:18     Задачи для тренировки и лучшего понимания
Закрытая тема Создать тему
Опции темы

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