Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/35: Рейтинг темы: голосов - 35, средняя оценка - 4.60
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1

Нули в конце записи n!

10.07.2012, 20:43. Показов 6597. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Эта программа вычисляет нули в конце записи факториала числа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <math.h>
long recourse(long n)                   //n - Число;
{
    long z=0,x;                         //z - счётчик, x - количество степеней пятёрки;
    for (int i=1;i<=10000;i++)
    {
        long long pwr=pow(5,i+.0);      //Подсчитываем максимальное количество степеней пятёрки(чтобы влазило в n)
        if (n<=pwr) { x=i; break; }     //Если степень пятёрки превосходит входное число, останавливаемся на прошлой;
    }
    for (int i=x;i>=1;i--)              //Начиная от максимальной степени 5-ки до первой, имеем...
    {
        z=z+n/pow(5,i+.0);              //Делим входное число на степени пятёрки и добавляем в счётчик;
    }
        return z;                       //Возвращаем значение: Нули в конце записи n!.
}
int main()
{
    long n;                             //Дано число n;
    scanf("%ld",&n);                    //Cчитываем;
    printf("%ld\n",recourse(n));        //Выводим количество нулей в конце числа n!.
}
Очередная задача: вывести количество нулей, находящиеся в k - ричной системе счисления. (k>=2>=36).
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.07.2012, 20:43
Ответы с готовыми решениями:

Нули в конце массива
Задание было заполнить массив случайными числами от -5 до 5. А также вычислить максимальный елемент массива. И сумму элементов ,...

Отсортировать заданную последовательность так, чтобы все нули оказались в конце
Задача: Дана последовательность чисел, отсортировать эту последовательность так, чтобы все нули оказались в конце, а все остальные числа...

Разместить в массиве все положительные элементы в начале, отрицательные - в конце, посередине - нули
Всем доброго времени суток! Большая просьба помочь написать программу. Нужно сформировать 2 одинаковых динамических одномерных массива, где...

12
 Аватар для UFO94
267 / 256 / 23
Регистрация: 04.04.2012
Сообщений: 546
10.07.2012, 22:43
Как вариант можно разложить на множители основание системы счисления, и каждое новое число в подсчете факториала тоже раскладывать. Далее подсчитываем количество каждого интересующего нас простого множителя, и получаем ответ. Возможно, и не самый рациональный путь...
Если нужно, могу написать код.
P.S.:
Цитата Сообщение от SeryZone Посмотреть сообщение
(k>=2>=36).
Что-то тут не так
0
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
10.07.2012, 23:20  [ТС]
Цитата Сообщение от UFO94 Посмотреть сообщение
Что-то тут не так
Да, извините, ошибся, вот настоящие ограничения: 2>=k>=5000
0
 Аватар для UFO94
267 / 256 / 23
Регистрация: 04.04.2012
Сообщений: 546
11.07.2012, 00:39
Ну, ограничения не принципиально. Код нужен?
0
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 10:30  [ТС]
Да. Сколько не думал - не получается.
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
11.07.2012, 11:12
Цитата Сообщение от SeryZone Посмотреть сообщение
Да. Сколько не думал - не получается.
Марсианский факториал?
0
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 11:23  [ТС]
Причём тут факториал? Количество нулей важно, а не сам факториал!
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
11.07.2012, 11:42
Цитата Сообщение от SeryZone Посмотреть сообщение
Причём тут факториал? Количество нулей важно, а не сам факториал!
Просто такая (марсианские факториалы) задача имеет вопрос : Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.
Тогда ладно
0
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 12:15  [ТС]
Да, да, всё правильно. В начале приводил код с десятичным основанием. Вводятся числа n и k. Ограничения известны.
0
 Аватар для UFO94
267 / 256 / 23
Регистрация: 04.04.2012
Сообщений: 546
12.07.2012, 02:08
Ну, возможно, я сейчас напишу не лучший код, но можно так: пусть k -- основание системы счисления. Тогда у k может быть не больше m1=log2k множителей (с округлением вниз до целых). Введем временный массив tmp размерa m1. При этом в переменную m2 считаем реальное количество множителей (без учета кратности). Реализация этого логического куска:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//...введение n,k и прочее
int m2=0;
int m1=log((float)k)/log(2);
int* tmp=new int[m1];
for(int i=0; i<m1; i++)
tmp[i]=0;
int k1=k;
int i=0;
while(k1!=1)
{
for(i=2; i<=k1; i++)
if(k1%i==0)
break;
tmp[m2]=i;
m2++;
}
Посчитаем количество разным множителей m, воспользовавшись тем, что множители отсортированы по нарастанию
C++
1
2
3
4
5
int m=1;
if(m2!=1)
for(i=0; i<m2-1; i++)
if(tmp[i]!=tmp[i+1])
m++;
Теперь перепишем наш временный массив в двухмерный 2*m. В каждом из m столбцов будет хранится делитель и его кратность. Например, число 600=2*2*2*3*5*5 запишется как
2 3 5
3 1 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
int* *mult=new int*[m];
for(i=0; i<m; i++)
mult[i]=new int[2];
if(m==1)
{
mult[0][0]=k;
mult[0][1]=1;
}
else
{
m1=0;
mult[0][0]=tmp[0];
mult[0][1]=1;
for(i=0; i<m2-1; i++)
{
if(tmp[i]==tmp[i+1])
mult[0][1]++;
else
{
m1++;
mult[m1][0]=tmp[i+1];
mult[m1][1]=1;
}
}
}
Осталось только посчитать число делителей числа k в n!.
Возьмем, к примеру, делитель 3. n/3 чисел из произведения n! делятся на 3. n/(3*3) -- делятся на 3 дважды, n/(3*3*3) -- трижды и т.д.
Реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int result=0;
if(m==1)
result=res(mult[0][0],n);
else
{
result=res(mult[0][0],n)/mult[0][1];
for(i=1; i<m; i++)
{
int res1=res(mult[i][0],n)/mult[i][1];
if(res1<result)
result=res1;
}
}
//... вывод ответа -- result.
C++
1
2
3
4
5
6
7
8
9
10
11
int res(int divider, int n)
{
int s=0;
int k=n/divider;
while(k!=0)
{
s+=k;
k/=divider;
}
return s;
}
Добавлено через 38 секунд
P.S.: Обращайтесь, если будут вопросы по коду.
1
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
18.07.2012, 14:31  [ТС]
Да, мало что понятно... Ну что ж, буду разбираться!
0
 Аватар для UFO94
267 / 256 / 23
Регистрация: 04.04.2012
Сообщений: 546
18.07.2012, 21:35
Если будете задавать вопросы станет понятнее. Так что именно не понятно?
1
 Аватар для SeryZone
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
18.07.2012, 22:41  [ТС]
Пока разберусь с реализацией, а потом, если что вопросы задам.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
18.07.2012, 22:41
Помогаю со студенческими работами здесь

Расположить элементы массива так, чтобы нули было в начале, а единицы в конце
Дан массив, состоящий из нулей и единиц, нужно расположить элементы массива так, чтобы нули было в начале, а единицы в конце.

Отсортировать массив таким образом, чтобы все нули находились в начале, а единицы — в конце массива
Здравствуйте, дано такое задание Элементами массива IM(N) являются числа 0 и 1. Отсортировать этот массив таким образом, чтобы все нули...

Отсортировать массив из 0 и 1 так, чтобы все нули находились в начале, а все единицы - в конце массива
Тема: Функции 1. Дано одномерный массив, заполненный 0 и 1 в произвольном порядке. Отсортировать данный массив таким образом, чтобы все...

Извлечь из записи целого числа нули
Извлеч из записи целого числа нули

Найти количество нулей в конце записи факториала N
Найти количество нулей в конце записи факториала числа n


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru