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

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

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

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

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

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

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

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

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

1272
no0ker
25.01.2011, 10:47     Задачи для тренировки и лучшего понимания
  #1161

Не по теме:

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

0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 10:59 1162
no0ker, А реализацию сделаете?
1
no0ker
25.01.2011, 11:27
  #1163

Не по теме:

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

0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 11:29 1164
no0ker, договорились.
1
Evg
25.01.2011, 11:39
  #1165

Не по теме:

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

1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 11:56 1166
Цитата Сообщение от Evg Посмотреть сообщение
потому великого комбинатора long double никак не спасёт)
полностью согласен
1
Эксперт С++
3204 / 1731 / 435
Регистрация: 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;
    }
}
4
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 15:01 1168
Mr.X, Извиняюсь, но проверочный сайт закрылся до 1 февраля. Проверить не смогу, но решение у Вас точно как у меня. Поэтому без тестов сообщаю, что Ваш код прошел бы все тесты.
1
Эксперт С++
3204 / 1731 / 435
Регистрация: 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;
    }    
}
1
101 / 88 / 7
Регистрация: 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 минут

Не по теме:

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

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

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

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

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

Добавлено через 3 минуты
и в чем недостатки моего метода? в том что нужно писать '*' постоянно?
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 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 Посмотреть сообщение
и в чем недостатки моего метода? в том что нужно писать '*' постоянно?
Если задача зачтена, то значит в ней недостатков нет. Может быть реализация немного лучше, может быть немного хуже, но самое главное что задача сдана.
1
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
25.01.2011, 20:26 1176
no0ker, ну на C++ же пишете, там принято ссылки для таких целей использовать - просто удобнее. А так никакой разницы, наверняка в одно и то же компилируется.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 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.
Вывод: достаточно хранить четыре последние ненулевые цифры.
2
Эксперт С++
4707 / 2532 / 753
Регистрация: 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
Я нашел эту же задачу на другом сайте где ее можно сдать. Опытным путем выяснил, что если хранить три последние ненулевые цифры, то все тесты тоже проходят. А если хранить две последние ненулевые цифры, то не все тесты проходят.
1
Эксперт С++
3204 / 1731 / 435
Регистрация: 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.

В своей выкладке я рассчитал достаточное количество цифр, т.е. страхующее нас от наихудшего случая. Разумеется, при каких-то условиях необходимое количество может быть меньше, но это никак не опровергает моих расчетов.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 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.
Как-нибудь так.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.01.2011, 13:18

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

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

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

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

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


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

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

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