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

C++

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

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

15.07.2010, 05:53. Просмотров 338324. Ответов 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
no0ker
25.01.2011, 10:47     Задачи для тренировки и лучшего понимания
  #1161

Не по теме:

сдается мне, что это на "длинную арифметику" это не тянет. чтобы последнее число узнать вообще byte хватит наверное. ну а последнее ненулевое может чуток побольше

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 10:59     Задачи для тренировки и лучшего понимания #1162
no0ker, А реализацию сделаете?
no0ker
25.01.2011, 11:27
  #1163

Не по теме:

в данное время на работе. с дежурства приду - напишу. понимаю, что слова без кода - пустое место, поэтому оформляю в оффтопик.

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 11:29     Задачи для тренировки и лучшего понимания #1164
no0ker, договорились.
Evg
25.01.2011, 11:39
  #1165

Не по теме:

Понятно, что задача на последнее ненулевое число НЕ относится к тем, что решаются в лоб. Но поскольку здесь зацепили long double, то могу сказать, что у long double мантисса составляет 64 бита. Т.е. в пределах 64-битных целых чисел представление long double будет точным (и ничем не отличающимся от unsigned long long). Но бОльшие числа хоть и можно представлять в виде long double, они уже будут НЕ точными (с окроглением и отбрасыванием младших разрядов), а потому великого комбинатора long double никак не спасёт)

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 11:56     Задачи для тренировки и лучшего понимания #1166
Цитата Сообщение от Evg Посмотреть сообщение
потому великого комбинатора long double никак не спасёт)
полностью согласен
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 14:46     Задачи для тренировки и лучшего понимания #1167
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
//////////////////////////////////////////////////////////////////////////////////////
//Последняя цифра N!
//(Время: 1 сек. Память: 16 Мб Сложность: 39%)
//
//Требуется найти последнюю ненулевую цифру числа N! = 1*2*3*…*N.
//Входные данные
//
//Входной файл INPUT.TXT содержит единственное натуральное число N (N<=9999).
//Выходные данные
//
//В выходной файл OUTPUT.TXT выведите ответ на задачу.
//
//Пример
//INPUT.TXT
//1
//OUTPUT.TXT
//1
//
//Пример
//INPUT.TXT
//5
//OUTPUT.TXT
//2
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
int  get_last_nonzero_digit_of_factorial(int N)
{
    int last_dig = 1;
    for(int  i = 2; i <= N; ++i)
    {
        last_dig *= i;
        while(last_dig % 10 == 0)
        {
            last_dig /= 10;
        }        
        last_dig %= 10000;
    }
    return last_dig % 10;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout << "N = ";
        int N = 0;
        std::cin >> N;
        
        std::cout << "Последняя ненулевая цифра факториала "
                  << N 
                  << ": "
                  << get_last_nonzero_digit_of_factorial(N)
                  << std::endl;
    }
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 15:01     Задачи для тренировки и лучшего понимания #1168
Mr.X, Извиняюсь, но проверочный сайт закрылся до 1 февраля. Проверить не смогу, но решение у Вас точно как у меня. Поэтому без тестов сообщаю, что Ваш код прошел бы все тесты.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 15:55     Задачи для тренировки и лучшего понимания #1169
Цитата Сообщение от valeriikozlov Посмотреть сообщение
сообщаю, что Ваш код прошел бы все тесты.
Спасибо за добрые вести.
Чтобы не вычислять минимальный модуль вручную, можно еще так сделать:
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
70
71
72
73
74
75
76
77
//////////////////////////////////////////////////////////////////////////////////////
//Последняя цифра N!
//(Время: 1 сек. Память: 16 Мб Сложность: 39%)
//
//Требуется найти последнюю ненулевую цифру числа N! = 1*2*3*…*N.
//Входные данные
//
//Входной файл INPUT.TXT содержит единственное натуральное число N (N<=9999).
//Выходные данные
//
//В выходной файл OUTPUT.TXT выведите ответ на задачу.
//
//Пример
//INPUT.TXT
//1
//OUTPUT.TXT
//1
//
//Пример
//INPUT.TXT
//5
//OUTPUT.TXT
//2
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
int  get_min_mod()
{     
    for(int  val = 10;; val *= 10)
    {
        bool  cont = false;
        for(int  dig = 2; dig <= 9; ++dig)
        {
            if(   val % dig == 0
               && val / dig % 10 != 0)
            {
                cont = true;
                break;
            }
        }
        if(!cont)  return val;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int  get_last_nonzero_digit_of_factorial(int  N, int  min_mod)
{
    int last_dig = 1;
    for(int  i = 2; i <= N; ++i)
    {
        last_dig *= i;
        while(last_dig % 10 == 0)
        {
            last_dig /= 10;
        }        
        last_dig %= min_mod;
    }
    return last_dig % 10;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
 
    int  min_mod = get_min_mod();
    for(;;)
    {
        std::cout << "N = ";
        int N = 0;
        std::cin >> N;
        
        std::cout << "Последняя ненулевая цифра факториала "
                  << N 
                  << ": "
                  << get_last_nonzero_digit_of_factorial(N, min_mod)
                  << std::endl;
    }    
}
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 17:28     Задачи для тренировки и лучшего понимания #1170
может быть вот так..

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>
#include <fstream>
 
 
void last5(int*a){
    while(*a%10==0) *a/=10;
    (*a)%=100000;
}
 
 
int main(){
        std::ifstream fin;
        std::ofstream fout;
        fin.open("input.txt");
        fout.open("output.txt");
        int n, i;
        int res=1;
        fin >> n;
        for(i=1;i<=n;i++){
            res*=i;
            last5(&res);
        }
        fout << res%10 << std::endl;
        fin.close();
        fout.close();
        return 0;
}
Добавлено через 5 минут

Не по теме:

=( по моему мое "решение" отнюдь не оригинально..

valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 17:39     Задачи для тренировки и лучшего понимания #1171
no0ker, Я уже писал что проверить не смогу, но на 100% уверен, что Ваше решение прошло бы все тесты.
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 18:19     Задачи для тренировки и лучшего понимания #1172
а можно один вопрос?

очевидно, что последнюю цифру в произведении многозначных чисел можно узнать легко.
например, *****4 х ********3 = **********2 (в таком случае и byte хватит)
но если нужна последняя ненулевая цифра. если мы будем хранить в процессе умножения
лишь последнюю цифру, можем попасть впросак.
например, **********2 х *********5 = ******?0
и при дальнейших вычислениях хранить 0 просто глупо.
теперь вопрос - сколько последних цифр нужно хранить. может быть 2. или 3. или 4. или 5. или больше. честно говоря,в математике я не силен. поэтому просто взял онлайн генератор факториалов. и опытным путем пришел к 5. =)

может быть кто то может толково объяснить этот момент - почему именно 5 цифр необходимо хранить?
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.01.2011, 19:21     Задачи для тренировки и лучшего понимания #1173
no0ker, так по уму писать надо:
C++
1
2
3
4
5
6
void last5(int &a){
    while(a%10==0) a/=10;
    a %= 100000;
}
...
last5(res)
Добавлено через 1 минуту
5 цифр достаточно хранить при таких ограничениях на N. Если бы было ограничение до 10^9, например, куда больше цифр хранить пришлось бы.
no0ker
101 / 88 / 4
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 19:40     Задачи для тренировки и лучшего понимания #1174
Хохол, не могли вы бы пояснить? я использовал указатели и передавал в функцию адрес переменной. вы предлагаете использовать ссылки?

у меня такое ощущение, что если бы было ограничение 99 - нужно было бы хранить 3 цифры. а 999 - 4 цифры. =)

Добавлено через 3 минуты
и в чем недостатки моего метода? в том что нужно писать '*' постоянно?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 20:11     Задачи для тренировки и лучшего понимания #1175
Цитата Сообщение от no0ker Посмотреть сообщение
а можно один вопрос?
Не можно, а нужно. Лучше в таких вопросах разобраться до конца.
Цитата Сообщение от no0ker Посмотреть сообщение
теперь вопрос - сколько последних цифр нужно хранить.
На этот вопрос я именно сейчас не отвечу. Скажу лишь что я когда писал свой код, то мне запомнилось что N<=9999 (не более четырехзначного числа) и я из-за этого ограничивался %10000.
Я кстати также хочу задать вопрос Mr.X: по какому принципу Вы вычисляли минимальный модуль вручную?
Кстати если его и вычислять так, то я бы написал так:
C++
1
        for(int  dig = 2; dig <= 5; ++dig)

Цитата Сообщение от no0ker Посмотреть сообщение
и в чем недостатки моего метода? в том что нужно писать '*' постоянно?
Если задача зачтена, то значит в ней недостатков нет. Может быть реализация немного лучше, может быть немного хуже, но самое главное что задача сдана.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.01.2011, 20:26     Задачи для тренировки и лучшего понимания #1176
no0ker, ну на C++ же пишете, там принято ссылки для таких целей использовать - просто удобнее. А так никакой разницы, наверняка в одно и то же компилируется.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 23:05     Задачи для тренировки и лучшего понимания #1177
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Я кстати также хочу задать вопрос Mr.X: по какому принципу Вы вычисляли минимальный модуль вручную?
Определим, какое максимальное количество нулей в конце может иметь число, чтобы частное от его деления нацело на какую-либо цифру уже не имело нулей в конце.
Очевидно, что если в конце числа n нулей, то число
10^n = 2^n * 5^n
должно разделиться нацело на эту цифру или ее множитель, и частное уже не должно содержать одновременно двоек и пятерок в качестве простых множителей.
При n = 4 такой цифры не существует, так как она должна быть равна как минимум 16, а при n = 3 такая единственная цифра – это 8.
Если число равно X = k * 1000, (1)
где k – это число без нулей в конце, то при делении на 8 получим:
Y = X / 8 = k * 1000 / 8 = k * 125. (2)
Очевидно, что это число не будет иметь нулей в конце, если число k нечетное.
Итак, число вида
Y = k * 125, где k нечетно
при умножении на цифру 8 дает число X c тремя нулями в конце.
Очевидно, что при таком умножении нам потребуется знать максимальное количество последних цифр числа Y.
Из (1) видно, что последняя ненулевая цифра числа X равна последней цифре числа k.
Если известны три последние цифры числа Y, т.е.
Y % 1000 = (k * 125) % (125 * 8) = (k % 8) * 125,
то мы сможем найти k только с точностью по модулю 8, т.е. значения k = 1 и k = 9 мы различить не сможем.
Если же известны четыре последние цифры числа Y, т.е.
Y % 10000 = (k * 125) % (125 * 80) = (k % 80) * 125, (3)
то из (3) получим последнюю цифру p числа k:
p = Y % 10000 / 125 % 10.
Вывод: достаточно хранить четыре последние ненулевые цифры.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 08:56     Задачи для тренировки и лучшего понимания #1178
Mr.X, Не согласен. По-моему здесь ошибка:
Y % 1000 = (k * 125) % (125 * 8) = (k % 8) * 125,
У меня получается так: Y % 1000 =(k % (125 * 8) ) * 125
Руководствовался таким фактом:
произведение двух чисел имеет тот же остаток от деления на m, что и произведение остатков от деления этих чисел на m
Я нашел эту же задачу на другом сайте где ее можно сдать. Опытным путем выяснил, что если хранить три последние ненулевые цифры, то все тесты тоже проходят. А если хранить две последние ненулевые цифры, то не все тесты проходят.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 11:11     Задачи для тренировки и лучшего понимания #1179
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mr.X, Не согласен. По-моему здесь ошибка:

У меня получается так: Y % 1000 =(k % (125 * 8) ) * 125
Руководствовался таким фактом:

Я нашел эту же задачу на другом сайте где ее можно сдать. Опытным путем выяснил, что если хранить три последние ненулевые цифры, то все тесты тоже проходят. А если хранить две последние ненулевые цифры, то не все тесты проходят.
Равенство
Y % 1000 = (k % 8) * 125
доказывается очень просто.
Y % 1000 = p
(1)
в сущности означает, что
Y = 1000 * n + p, где n – некоторое целое число, откуда
k * 125 = 1000 * n + p,
т.е.
k * 125 = 125 * 8 * n + p,
откуда
k = 8 * n + p / 125,
т.е.
k % 8 = p / 125,
откуда
p = (k % 8) * 125.
Подставляя в (1), получим
Y % 1000 = (k % 8) * 125,
что и требовалось доказать.

Из правила «произведение двух чисел имеет тот же остаток от деления на m, что и произведение остатков от деления этих чисел на m» следует не
Y % 1000 =(k % (125 * 8) ) * 125,
как у вас написано, а
Y % 1000 = (k * 125) % 1000 = (k % 1000 * 125) % 1000.
Непонятно только как вы собираетесь извлекать отсюда последнюю цифру числа k.
Например, при k = 1 и при k = 9 Y % 1000 = 125.

В своей выкладке я рассчитал достаточное количество цифр, т.е. страхующее нас от наихудшего случая. Разумеется, при каких-то условиях необходимое количество может быть меньше, но это никак не опровергает моих расчетов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2011, 13:18     Задачи для тренировки и лучшего понимания
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 13:18     Задачи для тренировки и лучшего понимания #1180
но это никак не опровергает моих расчетов.
полностью согласен.
Разумеется, при каких-то условиях необходимое количество может быть меньше
При любых условиях хватает хранить три последние ненулевые цифры. Эта задача довольно старая, тесты написаны грамотно и на все случаи жизни (по крайней мере я в этом не сомневаюсь).
Я вот еще раз перечитываю пост 1177 и не совсем понимаю, к чему там эти доказательства:
Итак, число вида
Y = k * 125, где k нечетно
при умножении на цифру 8 дает число X c тремя нулями в конце.
Очевидно, что при таком умножении нам потребуется знать максимальное количество последних цифр числа Y.
Из (1) видно, что последняя ненулевая цифра числа X равна последней цифре числа k.
Если известны три последние цифры числа Y, т.е.
Y % 1000 = (k * 125) % (125 * 8) = (k % 8) * 125,
то мы сможем найти k только с точностью по модулю 8, т.е. значения k = 1 и k = 9 мы различить не сможем.
Это вообще к чему написано? Вот это означает?:
Например очередное число A умножили на 125. В результате получилось число B. Если брать остаток от B всего три цифры, то получится одинаковый остаток если число A заканчивается на 1 или 9.
Если к этому, то это ни причем. Нам не нужно знать на какие цифры оканчивалось предыдущее число.

Mr.X, Можете привести наглядный пример, объясняющий Ваши вычисления?
Например такой (я объясню почему хранить одну последнюю цифру мало):
Очередное число получилось 12 (или оканчивается на 12). Нужно умножить на очередное число 5 (или которое оканчивается на 5). Если оставить одну последнюю цифру 2, то в полученном значении последняя ненулевая цифра 1. Если оставить две последних цифры, то в полученном значении последняя ненулевая цифра 6.
Как-нибудь так.
Yandex
Объявления
26.01.2011, 13:18     Задачи для тренировки и лучшего понимания
Закрытая тема Создать тему
Опции темы

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