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

C++

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

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

15.07.2010, 05:53. Просмотров 336201. Ответов 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
neske
1455 / 822 / 68
Регистрация: 26.03.2010
Сообщений: 2,811
17.08.2010, 22:06     Задачи для тренировки и лучшего понимания #721
nikkka, несомненно, с помощью функций сделать проще.
А классы, только ради практики.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Форумчанин
Эксперт С++
 Аватар для Kastaneda
4252 / 2784 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
18.08.2010, 11:48     Задачи для тренировки и лучшего понимания #722
Цитата Сообщение от nikkka Посмотреть сообщение
А вот очень старая, "класическая" задача о коне.
конь стоит в левом нижнем углу шахматной доски. ходит как обыно, Г-образно. надо обойти все клетки. НА ОДНУ КЛЕТКУ НЕЛЬЗЯ СТАНОВИТСЯ БОЛЕЕ ОДНОГО РАЗА. найдти количество ходов.
можно вывести на экран передвижения коня в "шахматной" записи, но это не обязательно.
Не давала она мне покоя, решил попробовать написать.
Пока был в отпуске тема разраслась до внушительных размеров, поэтому не знаю - решил ли ее кто -нибудь, а все перечитывать лень)
Вобщем вот, голову пришлось поломать) Начнем с того, что нужно просчитать 63 хода, конь потенциально имеет 8 ходов(вверх влево, вверх вправо и т.д.) таким образом нужно просчитать 8^63=много милиардов возможных ходов. (по крайней мере я подошел к решению этой задачи именно так)) Написал код, потом всеми доступными силами его оптимизировал (на сколько знаний хватило)). Результат - первые 12 ходов просчитывает достаточно быстро, 13ый ход уже подольше, 14ый около 30-40 минут, оставил программу работать на ночь) Утром (точнее в обед) проснулся, посмотрел сколько просчитала - 15(!) ходов всего! По самым скромным подсчетам на готовое решение уйдет несколько лет!
nikkka, вы где эту задачу взяли? Мне кажется как не крути, а быстрого решения нет! Могу ошибаться, поэтому хотелось бы услышать ваши коментарии по поводу этой задачи и, если в теме есть ее решение, дайте знать.

Не по теме:

Дома инет в блоке, пишу с чужого компа, кода по рукой нет, поэтому выложить его не могу. К сожалению ваши ответы прочитаю через несколько дней, когда денег на инет кину))

nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
18.08.2010, 12:02     Задачи для тренировки и лучшего понимания #723
Балада о нерешённой задачке, или как Kastaneda не дал себе покоя.
Об этой задачке мне впервые рассказал учитель информатики, когда я был в седьмом классе. Тогда программированием я не увлекался, так что не обратил внимания. Учитель сказал что это была его первая серьёзная решённая задачка. Позже, я всречал её на многих сайтах, но даже и не думал решать. Вообще то попробовал один раз, но ничего хорошого с этого не вышло .
Цитата Сообщение от Kastaneda Посмотреть сообщение
нужно просчитать 8^63 ... ходов
Не согласен. Число будет НАМНООООООООГО меньше. У 63-его хода, вообще будет один а не восемь вариантов. Ещё к примеру когда конь стоит на крайней клетке (к слову на А5), число возможных ходов будет 4, а не 8. К тому же, откуда в знаете что все 8 (или 4) клеток не были пройдены? 8^63 неверное число.
Задача на форуме ещё не решалась, но лично мне будет интересно посмотреть на код.
Цитата Сообщение от Kastaneda Посмотреть сообщение
Мне кажется как не крути, а быстрого решения нет!
Оно есть.
yanyk1n
 Аватар для yanyk1n
4326 / 1457 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.08.2010, 12:09     Задачи для тренировки и лучшего понимания #724
nikkka, раз пошёл разговор о шахматах, то есть ещё одна классическая задача (скорее всего, её тоже обсуждали)
На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
18.08.2010, 12:15  [ТС]     Задачи для тренировки и лучшего понимания #725
k1ry4, Обычно 8 ферзей. Так она и называется. Вроде бы где-то тут была
Kastaneda
Форумчанин
Эксперт С++
 Аватар для Kastaneda
4252 / 2784 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
18.08.2010, 12:15     Задачи для тренировки и лучшего понимания #726
Цитата Сообщение от nikkka Посмотреть сообщение
Не согласен. Число будет НАМНООООООООГО меньше. У 63-его хода, вообще будет один а не восемь вариантов. Ещё к примеру когда конь стоит на крайней клетке (к слову на А5), число возможных ходов будет 4, а не 8.
С таким подходом придется писать несколко ф-ций для проверки наличия хода под разные положения коня на шахмотной доске и в зависимости от него(положения) вызывать ту или иную ф-цию. Я же написал одну универсальную, которая проверяет все 8 ходов.
К тому же, откуда в знаете что все 8 (или 4) клеток не были пройдены?
Не понял смысла этих строк))
yanyk1n
 Аватар для yanyk1n
4326 / 1457 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.08.2010, 12:17     Задачи для тренировки и лучшего понимания #727
Lavroff, ну да, чаще всего дают разобрать частный случай N = 8. Но общий случай ещё никто не решал
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
18.08.2010, 12:20  [ТС]     Задачи для тренировки и лучшего понимания #728
k1ry4, Ну. Общий случай это как минимум жестоко)

Не по теме:

Ты в С++ перешел?)

yanyk1n
 Аватар для yanyk1n
4326 / 1457 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.08.2010, 12:26     Задачи для тренировки и лучшего понимания #729
Lavroff, ну даже частный для N >= 11 уже слишком

Не по теме:

Потихоньку, полегоньку

ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
18.08.2010, 12:36  [ТС]     Задачи для тренировки и лучшего понимания #730
k1ry4, Я почему-то не могу представить шахматную доску более чем 8 на 8... А что есть еще по шахматам?
yanyk1n
 Аватар для yanyk1n
4326 / 1457 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.08.2010, 12:47     Задачи для тренировки и лучшего понимания #731
Lavroff, есть ещё одна (подскажу, что тема - графы)
На телефонном аппарате имеется десять кнопок, расположенных следующим образом:
[1][2][3]
[4][5][6]
[7][8][9]
... [0] ...
Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом?

Всё зависит от конфигурации поля, можно придумать поизощрённее.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
18.08.2010, 20:11     Задачи для тренировки и лучшего понимания #732
Цитата Сообщение от k1ry4 Посмотреть сообщение
На телефонном аппарате имеется десять кнопок, расположенных следующим образом:
[1][2][3]
[4][5][6]
[7][8][9]
... [0] ...
Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом?
Наверное как-то так
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream cin("input.txt");
ofstream cout("output.txt");
 
typedef unsigned long long ull;
 
vector<vector<ull> > ans;
vector<vector<int> > g;
 
void buildGraph()
{
    const int N = 4, M = 3;
    const int a[N][M] = 
    {{1,2,3},
    {4,5,6},
    {7,8,9},
    {-1,0,-1}};
    g.resize(10);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if(a[i][j] != -1)
            {
#define check(di,dj) if(i + di >= 0 && j + dj >= 0 && \
                        i + di < N  && j + dj < M  && \
                        a[i+di][j+dj] != -1) \
                        g[a[i][j]].push_back(a[i+di][j+dj])
                check(1,2);
                check(2,1);
                check(-1,2);
                check(-2,1);
                check(-1,-2);
                check(-2,-1);
                check(1,-2);
                check(2,-1);
#undef check
            }
}
 
ull f(int digit, int len)
{
    if(ans[digit][len] == -1)
        if(len == 1)
            ans[digit][len] = 1;
        else
        {
            ans[digit][len] = 0;
            for(int i = 0; i < g[digit].size(); i++)
                ans[digit][len] += f(g[digit][i],len-1);
        }
    return ans[digit][len];
}
 
int main()
{
    int n;
    cin >> n;
    ans.resize(10,vector<ull>(n+1,-1));
    buildGraph();
    ull sum = 0;
    for(int i = 0; i < 10; i++)
        sum += f(i,n);
    cout << sum;
}
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
18.08.2010, 20:26     Задачи для тренировки и лучшего понимания #733
k1ry4, разве это как ни будь связанно с программированием?
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
18.08.2010, 22:22     Задачи для тренировки и лучшего понимания #734
Цитата Сообщение от k1ry4 Посмотреть сообщение
Lavroff, ну да, чаще всего дают разобрать частный случай N = 8. Но общий случай ещё никто не решал
Наверняка кто-то уже решил,ну не бывает так)
Скорее всего,у этой задачи есть математическое решение с использованием системы координат на плоскости (если речь шла про ферзей).
yanyk1n
 Аватар для yanyk1n
4326 / 1457 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.08.2010, 22:39     Задачи для тренировки и лучшего понимания #735
Цитата Сообщение от nikkka Посмотреть сообщение
k1ry4, разве это как ни будь связанно с программированием?
Очень связана с олимпиадным программированием, одна из классических задач
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
18.08.2010, 23:10     Задачи для тренировки и лучшего понимания #736
k1ry4, этож чисто мат. задачка. нужна расчётная формула, и только. нас же не просят вывести эти номера...
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
21.08.2010, 22:47  [ТС]     Задачи для тренировки и лучшего понимания #737
Числа Падавана (или как-то так), вчера ночью нашел. Интересная вещь. Похожи на Фибоначчи. Так вот. Хотелось бы увидеть решение итеративным методом. Рекурсивным делается элементарно, а вот насчет итеративного - хз. Рекурсивное решение внизу. Два варианта разного написания, алгоритм одинаковый.

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
#include <iostream>
 
typedef unsigned long long ULL;
 
ULL Pad(int n);
 
int main()
{
   int n=0;
   std::cout<<"Enter number of Padavan`s numb: ";
   std::cin>>n;
   std::cout<<"Padavan`s numb with number "<< n <<" is "<< Pad(n) <<'\n';
   return 0;
}
 
//ULL Pad(int n)
//{
//   if(n==0||n==1||n==2)
//      return 1;
//   else
//      return Pad(n-2)+Pad(n-3);
//}
 
ULL Pad(int n)
{
   return (n==0||n==1||n==2?1:Pad(n-2)+Pad(n-3));
}
silent_1991
Эксперт C++
4949 / 3025 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
22.08.2010, 02:09     Задачи для тренировки и лучшего понимания #738
Lavroff,
А у неё точно есть итеративное решение? А то я тут порасписывал для разных чисел - как-то неоднозначно получается, не видно явного алгоритма...
Просто в тех же числах Фибоначчи на каждом следующем шаге обязательно используется результат предыдущего (на то метод и итеративный), а здесь результат n-той итерации может потребоваться только ещё через m итераций... Потому без массива для хранения результатов всех предыдущих итераций, думаю, не обойтись... Но тогда теряется вся прелесть итеративного метода, и находится не n-тое число, а все до n включительно...
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
22.08.2010, 02:26  [ТС]     Задачи для тренировки и лучшего понимания #739
silent_1991, Вот и хочу узнать возможно это или нет. Потому что сам вчера пытался что-то придумать - не вышло
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.08.2010, 03:04     Задачи для тренировки и лучшего понимания
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4949 / 3025 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
22.08.2010, 03:04     Задачи для тренировки и лучшего понимания #740
Lavroff,
Вроде напал на след... Сейчас попытаюсь найти закономерность...

Добавлено через 32 минуты
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
#include <stdio.h>
 
int main()
{
    int n;
    int p0 = 1, p1 = 1, p2 = 1;
    int p, pm, pmplus1;
    int k;
    int i;
    
    printf("Enter number of Padavan`s numb: ");
    scanf("%d", &n);
    
    p = 1;
    (n % 2 == 0) ? (k = n / 2 - 1) : (k = n / 2);
    
    if (!(n == 0 || n == 1 || n == 2))
    {
        for (i = 0; i < k; i++)
        {
            pm = p1 + p0;
            pmplus1 = p2 + p1;
            p1 = pm;
            p0 = p2;
            p2 = pmplus1;
        }
 
        (n % 2 == 0) ? (p = pmplus1) : (p = pm);
    }
    
    printf("Padavan`s numb with number %d is %d\n", n, p);
    
    getch();
    return 0;
}
Добавлено через 4 минуты
Как видно, приходится за одну итерацию вычислять сразу два очередных числа - чётное и нечётное, т.к. каждое k-е число потребуется для вычисления только (k+2)-го и (k+3)-го чисел...
Yandex
Объявления
22.08.2010, 03:04     Задачи для тренировки и лучшего понимания
Закрытая тема Создать тему
Опции темы

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