Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.54/2345: Рейтинг темы: голосов - 2345, средняя оценка - 4.54
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562

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

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

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

Список задач, решение которых присутствует в данной теме:
44
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
15.07.2010, 05:53
Ответы с готовыми решениями:

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

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

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

1272
25.01.2011, 10:47

Не по теме:

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

0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
25.01.2011, 10:59
no0ker, А реализацию сделаете?
1
25.01.2011, 11:27

Не по теме:

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

0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
25.01.2011, 11:29
no0ker, договорились.
1
Evg
25.01.2011, 11:39

Не по теме:

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

1
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
25.01.2011, 11:56
Цитата Сообщение от Evg Посмотреть сообщение
потому великого комбинатора long double никак не спасёт)
полностью согласен
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 14:46
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;
    }
}
4
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
25.01.2011, 15:01
Mr.X, Извиняюсь, но проверочный сайт закрылся до 1 февраля. Проверить не смогу, но решение у Вас точно как у меня. Поэтому без тестов сообщаю, что Ваш код прошел бы все тесты.
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 15:55
Цитата Сообщение от 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;
    }    
}
1
101 / 88 / 7
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 17:28
может быть вот так..

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 минут

Не по теме:

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

1
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
25.01.2011, 17:39
no0ker, Я уже писал что проверить не смогу, но на 100% уверен, что Ваше решение прошло бы все тесты.
2
101 / 88 / 7
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 18:19
а можно один вопрос?

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

может быть кто то может толково объяснить этот момент - почему именно 5 цифр необходимо хранить?
0
Эксперт С++
 Аватар для Хохол
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
25.01.2011, 19:21
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, например, куда больше цифр хранить пришлось бы.
0
101 / 88 / 7
Регистрация: 17.12.2010
Сообщений: 416
25.01.2011, 19:40
Хохол, не могли вы бы пояснить? я использовал указатели и передавал в функцию адрес переменной. вы предлагаете использовать ссылки?

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

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

Цитата Сообщение от no0ker Посмотреть сообщение
и в чем недостатки моего метода? в том что нужно писать '*' постоянно?
Если задача зачтена, то значит в ней недостатков нет. Может быть реализация немного лучше, может быть немного хуже, но самое главное что задача сдана.
1
Эксперт С++
 Аватар для Хохол
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
25.01.2011, 20:26
no0ker, ну на C++ же пишете, там принято ссылки для таких целей использовать - просто удобнее. А так никакой разницы, наверняка в одно и то же компилируется.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
25.01.2011, 23:05
Цитата Сообщение от 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.
Вывод: достаточно хранить четыре последние ненулевые цифры.
2
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
26.01.2011, 08:56
Mr.X, Не согласен. По-моему здесь ошибка:
Y % 1000 = (k * 125) % (125 * 8) = (k % 8) * 125,
У меня получается так: Y % 1000 =(k % (125 * 8) ) * 125
Руководствовался таким фактом:
произведение двух чисел имеет тот же остаток от деления на m, что и произведение остатков от деления этих чисел на m
Я нашел эту же задачу на другом сайте где ее можно сдать. Опытным путем выяснил, что если хранить три последние ненулевые цифры, то все тесты тоже проходят. А если хранить две последние ненулевые цифры, то не все тесты проходят.
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 11:11
Цитата Сообщение от 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.

В своей выкладке я рассчитал достаточное количество цифр, т.е. страхующее нас от наихудшего случая. Разумеется, при каких-то условиях необходимое количество может быть меньше, но это никак не опровергает моих расчетов.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
26.01.2011, 13:18
но это никак не опровергает моих расчетов.
полностью согласен.
Разумеется, при каких-то условиях необходимое количество может быть меньше
При любых условиях хватает хранить три последние ненулевые цифры. Эта задача довольно старая, тесты написаны грамотно и на все случаи жизни (по крайней мере я в этом не сомневаюсь).
Я вот еще раз перечитываю пост 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.
Как-нибудь так.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.01.2011, 13:18

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
1180
Закрытая тема Создать тему
Новые блоги и статьи
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
alhaos 10.06.2026
Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .
[golang] Состояние гонки (race condition)
alhaos 10.06.2026
Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .
Взрослые отношения, и почему они не получаются
kumehtar 09.06.2026
Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .
[golang] Worker Pool
alhaos 09.06.2026
Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline
alhaos 08.06.2026
Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .
Свет внутри себя
kumehtar 07.06.2026
Пусть это будет здесь lIs4oanZS9Y
Программа для com-порта
Uhbif79 05.06.2026
Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[
anaschu 01.06.2026
Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru