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

C++

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

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

15.07.2010, 05:53. Просмотров 341694. Ответов 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++ Builder Прошу примеров для понимания INDY
C++ Нужен пример рекурсивной функции для понимания ее назначения и практической пользы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.01.2011, 22:07     Задачи для тренировки и лучшего понимания #1081
Хм... Странно... Скажите, например, в таком тесте ответ должен быть 7:
Код
10
1 2 3 2 5 6 2 8 9 2
?
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:12     Задачи для тренировки и лучшего понимания #1082
silent_1991, Да, ответ 7, мой код тоже выдал этот ответ.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.01.2011, 22:14     Задачи для тренировки и лучшего понимания #1083
valeriikozlov, ну это я просто пример привёл, чтобы понять, правильно ли понял задание... Вообще что-то не могу у себя найти ошибку... Всё вроде по заданию.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:17     Задачи для тренировки и лучшего понимания #1084
silent_1991, Вот контрпример:
6
1 24 2 26 3 4
У Вас выдает 3.
А нужно 4:
1 2 3 4
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
12.01.2011, 22:19     Задачи для тренировки и лучшего понимания #1085
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
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
   ifstream fin ("input.txt");
   ofstream fout ("output.txt");
   
    int n;
   fin >> n;
    vector <int> m; 
    for (int i = 0; i < n; i++)
    {
        int temp;
        fin >> temp;
        m.push_back(temp);
   }
 
    vector <int> a(n, 1);
    a[0] = 1;
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            if (m[j] < m[i])
                if (a[j]+1 > a[i])
                    a[i] = a[j]+1;
 
    fout << *max_element (a.begin(), a.end()) << endl;
 
    return 0;
}
первый тест точно проходит

Добавлено через 1 минуту
и второй
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:20     Задачи для тренировки и лучшего понимания #1086
Mayonez, Все тесты прошел Ваш код.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
12.01.2011, 22:24     Задачи для тренировки и лучшего понимания #1087
valeriikozlov, а откуда задачка? (у меня просто решение есть)
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:25     Задачи для тренировки и лучшего понимания #1088
Mayonez, отсюда: http://********/?main=task&id_task=122
кстати у меня похожее решение, только я делал тоже самое с конца, а не с начала.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.01.2011, 22:26     Задачи для тренировки и лучшего понимания #1089
valeriikozlov, да, тут по-другому надо решать... Походу, через динамику...
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:28     Задачи для тренировки и лучшего понимания #1090
silent_1991, через динамику точно получится.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.01.2011, 22:43     Задачи для тренировки и лучшего понимания #1091
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 <iostream>
#include <fstream>
 
int main()
{
    std::ifstream fin("input.txt");
 
    int nums[1000];
    int lens[1000] = {0};
    int N;
 
    fin >> N;
 
    for (int i = 0; i < N; ++i)
        fin >> nums[i];
 
    fin.close();
 
    for (int i = 0; i < N; ++i)
        for (int j = i - 1; j >= 0; --j)
            if (nums[j] < nums[i] && lens[j] + 1 > lens[i])
                lens[i] = lens[j] + 1;
 
    int max_len = lens[0];
 
    for (int i = 1; i < N; ++i)
        if (max_len < lens[i])
            max_len = lens[i];
 
    std::ofstream fout("output.txt");
 
    fout << max_len + 1;
 
    return 0;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:49     Задачи для тренировки и лучшего понимания #1092
silent_1991, Ваш код прошел все тесты.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.01.2011, 22:51     Задачи для тренировки и лучшего понимания #1093
valeriikozlov, честно говоря, пришлось чуток в код Mayonezа подсмотреть, я всё-таки в динамике ещё не очень хорошо ориентируюсь
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 23:59     Задачи для тренировки и лучшего понимания #1094
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от silent_1991 Посмотреть сообщение
я всё-таки в динамике ещё не очень хорошо ориентируюсь
Я попозже разбор этой задачи сделаю, но под свой код, думаю будет понятней как применяется здесь динамика.

Добавлено через 1 час 2 минуты
Разбор задачи Максимальная подпоследовательность
Я для решения этой задачи применил такой алгоритм:
Сначало каждому числу последовательности сопоставил число 1 (эти числа в дальнейшем будут обозначать - максимальную длину возрастающей подпоследовательности начинающейся с этого числа). Т.е изначально получилось (привожу пример из задачи):
3 29 5 5 28 6
1 1 1 1 1 1 (для удобства числа этой строки назовем max_len)
Затем начинаем со второго числа с конца (в данном случае с 28) и идем к начальному числу. Для каждого числа делаем проверку так:
- перебираем все числа, которые находятся справа от проверяемого числа. Если проверяемое число оказывается меньше числа которое перебираем и max_len у проверяемого числа меньше чем max_len+1 числа которое перебираем, то max_len (проверяемого числа) делаем (max_len числа которое перебираем) + 1.
По сути мы очередное проверяемое число таким образом прикрепляем к самой длинной уже существующей подпоследовательности и эту длину сохраняем в переменной max_len для этого числа.
После такого перебора осталось только найти максимальное max_len. Это и будет результат.
silent_1991
13.01.2011, 08:44
  #1095

Не по теме:

valeriikozlov, нет, я всё же нагло копипастить код у Mayonezа не стал, просто посмотрел одну вещь, а так разобрался, как решается задача, иначе не стал бы выкладывать код.

valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
13.01.2011, 18:15     Задачи для тренировки и лучшего понимания #1096
Туристическое агентство
(Время: 5 сек. Память: 32 Мб Сложность: 80%)

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

Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B,C), таких что любой путь с планеты B на планету C проходит через планету A.

Помогите Антону!
Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2 <= N <= 20 000, 1 <= M <= 200 000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.
Выходные данные

В выходной файл OUTPUT.TXT выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A.
Пример:
INPUT.TXT

7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
OUTPUT.TXT
18
6
6
6
6
6
6

От себя: Это очень сложная задача. Она по сложности не сравнима с предыдущими задачами. Я сам ее пытался решить применив несколько различных алгоритмов. Вся сложность была в том что бы уложиться по времени.
Я выкладываю условие этой задачи на 10 дней. Если кто-то решит ее в течении этого срока, то я обещаю что пройдусь по всем темам где этот человек писал посты и нажму ему по максимуму кнопку "спасибо" (насколько хватит ограничения сайта) (если честно, то отдал бы ему все свои очки репутации не задумываясь). По истечении 10 дней обязательно выложу свой алгоритм решения задачи (чуствую придется потрудится, порисовать, но эта задача этого заслуживает).
Условие задач попроще все равно буду стараться выкладывать и в течении этих 10 дней.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
13.01.2011, 19:23     Задачи для тренировки и лучшего понимания #1097
Мда, O(NM) не катит.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 16:13     Задачи для тренировки и лучшего понимания #1098
Цитата Сообщение от Хохол Посмотреть сообщение
Мда, O(NM) не катит.
точно. (но кстати вариант который я сдал на самом долгом тесте имел время 0,638 секунды).

Добавлено через 22 часа 55 минут
Сообщество роботов
(Время: 1 сек. Память: 16 Мб Сложность: 30%)

Сообщество роботов живет по следующим законам:
- один раз в начале года они объединяются в группы по три или пять роботов;
- за год группа из трех роботов собирает 5 новых, а группа из 5 роботов – 9 новых;
- роботы объединяются так, чтобы собрать за год наибольшее количество новых роботов;
- каждый робот живет ровно три года после сборки.

В начале первого года было K роботов и все они были только что собраны.

Требуется написать программу, которая найдет количество роботов в начале N-го года.
Входные данные

Входной файл INPUT.TXT содержит записанные через пробел числа K (1 <= K <= 500) и N (1 <= N <= 100).
Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число - количество роботов в начале N-го года. Количество роботов меньше, чем 2^31.
Пример:
INPUT.TXT

3 2
OUTPUT.TXT
8

Пример:
INPUT.TXT

8 2
OUTPUT.TXT
22

Добавлено через 20 часов 38 минут
Разбор задачи Сообщество роботов.
В целом вся задача заключается в том как за год собрать наибольшее количество роботов.
Если провести небольшой анализ, то получится что нужно делать так:
- имеющееся число роботов (на данный год) разбиваем на пятерки.
- количество оставшихся роботов (не вошедших в число пятерок), делим на тройки.
- если количество оставшихся роботов после такого деления на пятерки и тройки равно нулю, то вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.
- если количество оставшихся роботов после такого деления на пятерки и тройки не равно нулю, то удаляем по одной каждую пятерку (пока нам это позволяет количество пятерок) и пытаемся с имеющимися остатками роботов разбить их на тройки, что бы не было остатков роботов вообще. После этого тоже вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
16.01.2011, 14:17     Задачи для тренировки и лучшего понимания #1099
может быть вот так

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
68
69
#include <stdio.h>
 
 
int new_d(int n){
    int i,j,res=0;
    
    for(i=n/5, j=(n-5*i)/3; i>=0; i--, j=(n-5*i)/3){
        if ( i*5+j*3==n ) {
            res=i*9+j*5;
            return res;
        }
        else {
            if (res < i*9 + j*5) res = i*9 + j*5;
        };
    };
 
    return res;
}
 
 
 
main(){
    
    __int64 n;
    int year,year_end;
    int d=0, dd=0, ddd=0, dddd=0;
    
    FILE *fin,*fout;
    fin=fopen("INPUT.TXT","r");
    fout=fopen("OUTPUT.TXT","w");
    fscanf(fin,"%I64d %d",&n,&year_end);
    
    
    d=n;
    
    if(n<3 && year_end<4){
        fprintf(fout,"%d",n);
    
        fclose(fin);
        fclose(fout);
        return 0;
    }
    
    if(n<3 && year_end>4){
        fprintf(fout,"%d",0);
    
        fclose(fin);
        fclose(fout);
        return 0;
    }
    
    
    for(year=1; year<year_end; year++){
        dddd=ddd;
        ddd=dd;
        dd=d;
        d=new_d(n);
        n+=d;
        n-=dddd;
    }
    
    
    printf("%I64d",n);
    fprintf(fout,"%I64d",n);
    
    fclose(fin);
    fclose(fout);
    
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2011, 17:21     Задачи для тренировки и лучшего понимания
Еще ссылки по теме:
C++ Киньте задачки для тренировки
Дайте задания для тренировки C++
Книги для тренировки/развития котелка и просто убийства времени C++
C++ Какой компилятор выбрать для лучшего изучения С++ по книге Берна Страуструпа?п
На соревнованиях по фигурному катанию оценки заносятся в компьютер. Составить программу для вывода на экран лучшего результата после каждого выступлен C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 17:21     Задачи для тренировки и лучшего понимания #1100
no0ker, Ваш код прошел все тесты.
Yandex
Объявления
16.01.2011, 17:21     Задачи для тренировки и лучшего понимания
Закрытая тема Создать тему
Опции темы

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