Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.88/2010: Рейтинг темы: голосов - 2010, средняя оценка - 4.88
В астрале
Эксперт С++
8022 / 4779 / 654
Регистрация: 24.06.2010
Сообщений: 10,554
1

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

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

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

Список задач, решение которых присутствует в данной теме:
43
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.07.2010, 05:53
Ответы с готовыми решениями:

Элементарные программы, для лучшего понимания языка...
Здравствуйте. Вот сегодня решил что пора изучать с++. Есть пару задач. Начал решать и уже на первой...

Задачи для тренировки и лучшего понимания языка
Предлагаю в этой теме размещать задачи, которые помогут новичкам (и не только) более детально...

Литература для лучшего понимания сути программирования
Привет! Подскажите литературу, которая поможет разобраться в сути самого процесса программирования,...

Набор задачь для тренировки и улучшения понимания программирования
Добрый вечер всем. Если кто знает модскажите где можно найти подобный набор задачь...

1272
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
12.01.2011, 22:07 1081
Хм... Странно... Скажите, например, в таком тесте ответ должен быть 7:
Код
10
1 2 3 2 5 6 2 8 9 2
?
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:12 1082
silent_1991, Да, ответ 7, мой код тоже выдал этот ответ.
1
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
12.01.2011, 22:14 1083
valeriikozlov, ну это я просто пример привёл, чтобы понять, правильно ли понял задание... Вообще что-то не могу у себя найти ошибку... Всё вроде по заданию.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 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
1
387 / 279 / 53
Регистрация: 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 минуту
и второй
1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:20 1086
Mayonez, Все тесты прошел Ваш код.
1
387 / 279 / 53
Регистрация: 26.12.2009
Сообщений: 875
12.01.2011, 22:24 1087
valeriikozlov, а откуда задачка? (у меня просто решение есть)
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:25 1088
Mayonez, отсюда:
кстати у меня похожее решение, только я делал тоже самое с конца, а не с начала.
1
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
12.01.2011, 22:26 1089
valeriikozlov, да, тут по-другому надо решать... Походу, через динамику...
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:28 1090
silent_1991, через динамику точно получится.
0
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
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;
}
1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
12.01.2011, 22:49 1092
silent_1991, Ваш код прошел все тесты.
1
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
12.01.2011, 22:51 1093
valeriikozlov, честно говоря, пришлось чуток в код Mayonezа подсмотреть, я всё-таки в динамике ещё не очень хорошо ориентируюсь
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 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. Это и будет результат.
3
silent_1991
13.01.2011, 08:44
  #1095

Не по теме:

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

1
Эксперт С++
4707 / 2532 / 753
Регистрация: 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 дней.
0
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
13.01.2011, 19:23 1097
Мда, O(NM) не катит.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 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 минут
Разбор задачи Сообщество роботов.
В целом вся задача заключается в том как за год собрать наибольшее количество роботов.
Если провести небольшой анализ, то получится что нужно делать так:
- имеющееся число роботов (на данный год) разбиваем на пятерки.
- количество оставшихся роботов (не вошедших в число пятерок), делим на тройки.
- если количество оставшихся роботов после такого деления на пятерки и тройки равно нулю, то вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.
- если количество оставшихся роботов после такого деления на пятерки и тройки не равно нулю, то удаляем по одной каждую пятерку (пока нам это позволяет количество пятерок) и пытаемся с имеющимися остатками роботов разбить их на тройки, что бы не было остатков роботов вообще. После этого тоже вычисляем сколько роботов было собрано в этом году этими пятерками и тройками.
0
101 / 88 / 7
Регистрация: 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);
    
}
1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 17:21 1100
no0ker, Ваш код прошел все тесты.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.01.2011, 17:21

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Проверить на правильность и закомментировать весь код для лучшего понимания
Всем здравствуйте. Условие задачи - Заданная матрица целых чисел размером (N, N). Найти среднее...

Нужны задачи для тренировки
Киньте задачки на классы......а то в самоучителе, по которому я учу Сишку....приведены задачки,...

Нужны задачи для тренировки
Здравствуйте киньте пожалуйста задания по с++ для человека начинающего изучать Turbo с++

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


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

Или воспользуйтесь поиском по форуму:
1100
Закрытая тема Создать тему
Опции темы

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