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

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

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

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

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

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

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

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

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

1272
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 14:35 1181
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mr.X, Можете привести наглядный пример, объясняющий Ваши вычисления?
Ну, вообще-то я старался изложить свои вычисления как можно более логично, поэтому жаль, что что-то осталось непонятным.
А пример из процитированного вами отрывка следует тот, что числа вида
Y = k * 125, где k нечетно
имеют последние три цифры 125, 375, 625 или 875.
При умножении каждого такого числа на 8 для определения последней ненулевой цифры знания этих последних трех цифр недостаточно, например
125 * 8 = 1000
1125 * 8 = 9000
2125 * 8 = 17000 и т.д.,
т.е. из того, что три последние цифры равны 125, следует только, что последняя ненулевая цифра равна 1 по модулю 8. Поэтому в этом случае нужно знать как минимум четыре цифры.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 15:14 1182
Mr.X, Все понял. Тогда в защиту трех цифр могу сказать следующее:
Когда мы достигнем очередного числа, что его можно разложиьт так:
Y = k * 125, где k целое число,
то к этому времени k точно будет целым. Видимо поэтому хватает знать три последних цифры.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 15:24 1183
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mr.X, Все понял. Тогда в защиту трех цифр могу сказать следующее:
Когда мы достигнем очередного числа, что его можно разложиьт так:
Y = k * 125, где k целое число,
то к этому времени k точно будет целым. Видимо поэтому хватает знать три последних цифры.
Интересно, но непонятно. Можете пояснить что вы имели в виду?
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 15:56 1184
Mr.X, Все очередные числа мы получаем так:
- Сначало очередное число 1.
- умножаем его на 2, получаем очередное число 2
- умножаем его на 3, получаем очередное число 6
и т.д.
Т.е
Когда мы достигнем очередного числа, что его можно разложить так:
Y = k * 125, где k целое число,
Это будет, когда мы дойдем до умножения на 15, тогда получим очередное число, которое можно так представить (У него в разложении на простые множители будет три множителя равные 5).
Но k в этом случае будет четным (ведь мы использовали в формировании этого очередного числа много четных множителей).
А вообще-то если применять операцию %10000 или %1000 к очередному числу то скорее всего очередное число никогда нельзя будет представить ввиде Y = k * 125, где k целое число
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 16:47 1185
Цитата Сообщение от valeriikozlov Посмотреть сообщение
ведь мы использовали в формировании этого очередного числа много четных множителей
Мда. Вот то, что все факториалы четные, я как раз и упустил. Четыре цифры нужно при умножении нечетного числа на 8, поэтому для факториалов это неактуально, и для них достаточно 3 цифры.
Так что вы оказались правы.
1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 16:54 1186
Mr.X, Извиняюсь, но у меня пара опечаток в предыдущих сообщениях:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Когда мы достигнем очередного числа, что его можно разложить так:
Y = k * 125, где k целое число,
то к этому времени k точно будет целым.
Нужно читать так:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Когда мы достигнем очередного числа, что его можно разложить так:
Y = k * 125, где k целое число,
то к этому времени k точно будет четным.
Это называется заработался.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 19:04 1187
Цитата Сообщение от Mr.X Посмотреть сообщение
Мда. Вот то, что все факториалы четные, я как раз и упустил. Четыре цифры нужно при умножении нечетного числа на 8, поэтому для факториалов это неактуально, и для них достаточно 3 цифры.
Так что вы оказались правы.
valeriikozlov, что-то вы сбили меня с панталыку. Ведь мы же последние ненулевые цифры факториала рассматриваем. Так что если факториал оканчивается нулями, и их отбросить, то получившееся число теоретически может быть и нечетным, так что мои рассуждения остаются в силе.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 19:39 1188
Цитата Сообщение от Mr.X Посмотреть сообщение
valeriikozlov, что-то вы сбили меня с панталыку. Ведь мы же последние ненулевые цифры факториала рассматриваем. Так что если факториал оканчивается нулями, и их отбросить, то получившееся число теоретически может быть и нечетным, так что мои рассуждения остаются в силе.
Хорошо давайте так: что такое полученный 0 в конце числа. Это или умножение 2*5 (имею ввиду что очередное умножаемое число оканчивается на 2 (или любую четную цифру), а очередное число на которое умножаем оканчивается на 5. Или наоборот.) или умножение на число оканчивающееся на 0.
Сколько у нас четных чисел до первой пятерки? Два (это числа 2 и 4). Т.е. когда очередное число умножаем на 5, то оно содержит в своем разложении на простые множители уже три простых числа 2. Удалив этот очередной 0 из числа мы удаляем таким образом одну 5-ку и одну 2-ку.
Но двоек гораздо больше чем пятерок при вычислении факториала числа.
Вот можете проверить:
5!=120 (до получения этого числа также использованы множители 2 и 4. Т.е. всего в составе 5! имеются три 2-ки)
отнимаем один ноль (на самом деле одну 5-ку и одну 2-ку). Остается 12 (в этом числе остались две 2-ки).
или
10!=3628800 (до получения этого числа использованы множители 2, 4, 6, 8 и само число 10. Т.е. всего в составе 10! восемь 2-ек). Отнимаем 2 нуля (две 5-ки и две 2-ки). Остается 36288. В этом числе остались шесть двоек.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.01.2011, 22:05 1189
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Хорошо давайте так: что такое полученный 0 в конце числа. Это или умножение 2*5 (имею ввиду что очередное умножаемое число оканчивается на 2 (или любую четную цифру), а очередное число на которое умножаем оканчивается на 5. Или наоборот.) или умножение на число оканчивающееся на 0.
Сколько у нас четных чисел до первой пятерки? Два (это числа 2 и 4). Т.е. когда очередное число умножаем на 5, то оно содержит в своем разложении на простые множители уже три простых числа 2. Удалив этот очередной 0 из числа мы удаляем таким образом одну 5-ку и одну 2-ку.
Но двоек гораздо больше чем пятерок при вычислении факториала числа.
Вот можете проверить:
5!=120 (до получения этого числа также использованы множители 2 и 4. Т.е. всего в составе 5! имеются три 2-ки)
отнимаем один ноль (на самом деле одну 5-ку и одну 2-ку). Остается 12 (в этом числе остались две 2-ки).
или
10!=3628800 (до получения этого числа использованы множители 2, 4, 6, 8 и само число 10. Т.е. всего в составе 10! восемь 2-ек). Отнимаем 2 нуля (две 5-ки и две 2-ки). Остается 36288. В этом числе остались шесть двоек.
Ну, это все нестрогие рассуждения.
Вы можете вычислить в своей программе (сохраняя четыре последние ненулевые цифры), чему будут равны эти цифры для факториала числа 390627 ?

Добавлено через 1 час 37 минут
valeriikozlov, можете посчитать чему равна последняя ненулевая цифра факториала числа 375, сохраняя сначала 3, а затем 4 ненулевые цифры. У меня получились интересные результаты.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2011, 08:11 1190
Цитата Сообщение от Mr.X Посмотреть сообщение
valeriikozlov, можете посчитать чему равна последняя ненулевая цифра факториала числа 375, сохраняя сначала 3, а затем 4 ненулевые цифры. У меня получились интересные результаты.
Я еще не делал (примерно через час смогу это сделать). Пока могу догадаться что было так:
k перед умножение на 375 было четным. При умножении на 375 стало нечетным (возможно). Но это нечетное k при следующем же умножении стало четным. (Т.е. нечетное k хоть и получается иногда, но с числами кратными 125 его умножения мы не дождемся)

Добавлено через 1 час 33 минуты
Вы можете вычислить в своей программе (сохраняя четыре последние ненулевые цифры), чему будут равны эти цифры для факториала числа 390627 ?
Если пользоваться int то не могу (промежуточные значения не влазят в int), если воспользоваться long long то получается 4 (кстати проверил сохраняя 6 последних ненулевых цифр ответ тот же).

valeriikozlov, можете посчитать чему равна последняя ненулевая цифра факториала числа 375, сохраняя сначала 3, а затем 4 ненулевые цифры. У меня получились интересные результаты.
Я немного не так сделал. Сначало проверял сохраняя последние 4 ненулевые цифры и выяснил что при вычисления 9999! получается 4 момента когда last_dig становится нечетным. Все 4 случая оказались после умножения на i кратное 125. Но еще выяснил что во всех 4-х случаях last_dig становился четным до того момента когда i снова становилась кратной 5.
При сохранении 3 ненулевых цифр выяснил что таких случаев 23 (в том числе и когда i равна 375). Но как и в предыдущем случае last_dig становился четным до того момента когда i снова становилась кратной 5.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.01.2011, 10:01 1191
valeriikozlov, так вы можете сообщить чему у вас получилась равна последняя цифра в факториале 375 при сохранении трех цифр?
1
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2011, 12:25 1192
Цитата Сообщение от Mr.X Посмотреть сообщение
valeriikozlov, так вы можете сообщить чему у вас получилась равна последняя цифра в факториале 375 при сохранении трех цифр?
Mr.X, поздравляю Вы что называется "сорвали Джекпот".
По крайней мере здесь:
http://www.e-olimp.com.ua/problems-class/
нет такого теста, именно там у меня прошел вариант с сохранением 3-х последних цифр все тесты. Кстати я где-то ранее писал, что этот сайт не очень хорош по набору тестов (вот еще одно подтверждение).
А другой сайт, который считаю в этом плане хорошим, на котором я всегда проверял решения, я уже писал закрылся до 1 февраля. Как откроется, обязательно проверю. Посмотрим как там с этим тестом.

Добавлено через 23 минуты
Mr.X,
Я даже больше скажу. Оказывается для этой задачи мало и 4-х последних цифр запоминать. Точно хватит минимум 6-ти последних цифр. В доказательство запустите Ваш немного переделанный код и введите N=9999:
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
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
int  get_last_nonzero_digit_of_factorial(int N)
{
    __int64 last_dig = 1; // в этой переменной будем хранить последние 6 цифр
    __int64 last_dig2 = 1;// в этой переменной будем хранить последние 5 цифр
    for(int  i = 2; i <= N; ++i)
    {
        last_dig *= i; last_dig2 *= i;
        while(last_dig % 10 == 0)
        {
            last_dig /= 10;
        }        
        last_dig %= 1000000;
        while(last_dig2 % 10 == 0)
        {
            last_dig2 /= 10;
        }        
        last_dig2 %= 100000;
        if(last_dig2%10!=last_dig%10)// если последние цифры не совпадают
        {
            std::cout<<last_dig<<"      "<<last_dig2<<"          "<<i<<std::endl;
        }
    }
    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;    }
}
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.01.2011, 15:20 1193
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mr.X, поздравляю Вы что называется "сорвали Джекпот".
По крайней мере здесь:
http://www.e-olimp.com.ua/problems-class/
нет такого теста, именно там у меня прошел вариант с сохранением 3-х последних цифр все тесты. Кстати я где-то ранее писал, что этот сайт не очень хорош по набору тестов (вот еще одно подтверждение).
Что-то я не понял что вы имели в виду под Джекпотом. Там на сайте что ли призы дают за нахождение ошибок в их тестах?
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Я даже больше скажу. Оказывается для этой задачи мало и 4-х последних цифр запоминать. Точно хватит минимум 6-ти последних цифр.
Ох и любите вы скоропалительные заявления. Я уже не уверен, что существует количество цифр, достаточное для всех факториалов. Пока можно сказать, что шести цифр достаточно для факториалов с количеством цифр не больше 100000.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2011, 15:34 1194
Что-то я не понял что вы имели в виду под Джекпотом. Там на сайте что ли призы дают за нахождение ошибок в их тестах?
вряд-ли. Насколько мне известно, то нет.
Ох и любите вы скоропалительные заявления. Я уже не уверен, что существует количество цифр, достаточное для всех факториалов. Пока можно сказать, что шести цифр достаточно для факториалов с количеством цифр не больше 100000.
Я для конкретной задачи (когда N<=9999). Именно для этой задачи мало и 4-х цифр и 5-ти цифр. Хватает точно 6-ти.
Кстати не можете более подробно расшифровать фразу:
для факториалов с количеством цифр не больше 100000
Вы имеете ввиду значение N или значение N!
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.01.2011, 15:43 1195
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вы имеете ввиду значение N или значение N!
Я имел в виду количество цифр в N!.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
28.01.2011, 08:39 1196
Mr.X, Если Вас заинтересует, то есть решение, когда можно хранить всего одну последнюю ненулевую цифру (может быть это звучит немного фантастично, после всех приведенных неудачных теорий). Проверил практически правильность результатов до N=9999.
0
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.01.2011, 09:50 1197
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mr.X, Если Вас заинтересует, то есть решение, когда можно хранить всего одну последнюю ненулевую цифру (может быть это звучит немного фантастично, после всех приведенных неудачных теорий). Проверил практически правильность результатов до N=9999.
Расскажите, очень интересно.
0
Эксперт С++
4707 / 2532 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
28.01.2011, 10:37 1198
Суть решения заключается вот в чем:
При умножении двух различных чисел последняя ненулевая цифра всегда равна цифре, которая получается если умножить между собой только две последних ненулевых цифры этих чисел. Это правило характерно для всех умножаемых чисел, за исключением чисел оканчивающихся на цифру 5.
Примеры:
9246*427=36503596332
или 6*7=42
У обоих получившихся чисел последнее число равно 2
Для чисел оканчивающихся на цифру 5, такой вариант бывает не проходит, например:
12*5=60
2*5=10
Получается все дело в последней цифре перемножаемых чисел - равны они 5-ке или нет.
Можете сами подумать над этим, или потестировать, но это факт:
При умножении двух различных чисел последняя ненулевая цифра всегда равна цифре, которая получается если умножить между собой только две последних ненулевых цифры этих чисел. Это правило характерно для всех умножаемых чисел, за исключением чисел оканчивающихся на цифру 5.
Вот код с сохранением только последней ненулевой цифры (все входящие простые множители 5 (в число N!), объединяются с простыми множителями 2):
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
#include <stdio.h>
 
int main(){
   int n, i, j, k=5, km=0, f=1;
     freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
 
   scanf("%d", &n);
   while(n/k>0)
   {
       km+=n/k;
       k*=5;
   }
   for(i=2; i<=n; i++)
   {
       j=i;
       while(j%5==0)
       {
           j/=5;
       }
           while(km>0 && j%2==0)
           {
               km--;
               j/=2;
           }
           f=(f*(j%10))%10;       
   }
   printf("%d", f);               
        return 0;
}
1
Эксперт С++
3204 / 1731 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
29.01.2011, 09:52 1199
Цитата Сообщение от valeriikozlov Посмотреть сообщение
При умножении двух различных чисел последняя ненулевая цифра всегда равна цифре, которая получается если умножить между собой только две последних ненулевых цифры этих чисел. Это правило характерно для всех умножаемых чисел, за исключением чисел оканчивающихся на цифру 5.
Да, решение простое, но почему-то сразу не пришло никому в голову.
На самом деле ноль получается при перемножении пятерки и четной цифры. В данном случае пятерок меньше, поэтому убираем их, а так можно было бы и двойки убрать, а пятерки оставить.
Вот так работает примерно на четверть быстрее:
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
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
typedef long long  T_num;
/////////////////////////////////////////////////////////////////////////////////////////
T_num  get_last_nonzero_dig(T_num  n)
{
    const int _2_COUNT_MOD  = 4;
    T_num     _2_count      = 0;   
    T_num     _5_fact       = 5;
 
    while(n / _5_fact > 0)
    {
       _2_count -= n / _5_fact;
       _5_fact  *= 5;
    }
    if(_2_count)
    {        
        ++(--_2_count %= _2_COUNT_MOD);
        if(_2_count < 0)
        {
            _2_count += _2_COUNT_MOD;
        }    
    }
 
    T_num  res = 1;
 
    while(_2_count--)
    {
        res = res * 2 % 10;
    }
 
    for(T_num i = 2; i <= n; ++i)
    {
        T_num  j = i;
 
        while(j % 5 == 0)
        {
            j /= 5;
        }
 
        res = res * (j % 10) % 10;        
    }
    
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
    T_num  n = 0;
    for(;;)
    {
        std::cout << std::endl
                  << std::endl
                  << std::endl
                  << "n = ";
        std::cin >> n; 
        if(n <= 0) break;     
        std::cout << "Последняя цифра факториала "
                  << n 
                  << " равна "
                  << get_last_nonzero_dig(n)                  
                  << std::endl;   
    }
}
Добавлено через 4 минуты
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Проверил практически правильность результатов до N=9999.
Из математического обоснования следует, что программа будет считать правильно для любых факториалов.
0
4194 / 1787 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
29.01.2011, 16:49 1200
Цитата Сообщение от HIMen Посмотреть сообщение
Lavroff, Дан целочисленный массив, наподобие такого {1, 7, 3, 7, 8, 1, 3}. Все его элементы, кроме одного повторяются ровно 2 раза (две 1, две 7, две 3, но одна 8). Найти это не повторяющееся число. Числа и размер массива могут быть любыми.
Решение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int FindNoRepeat(int *a, int n)
{
 int *p1,*p2;
 bool f;
 for (p1=a+n-1; p1>a; --p1)
 {
  for (p2=p1-1, f=true; p2>=a; --p2)
  {
   if (*p1==*p2)
   {
    p1=p2-1;
    f=false;
    break;
   }
  }
  if (f)
  {
   return *p1;
  }
 }
 return a[0];
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.01.2011, 16:49

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

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

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

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

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


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

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

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