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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 5.00
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
10.07.2012, 20:43     Нули в конце записи n! #1
Эта программа вычисляет нули в конце записи факториала числа:
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).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
10.07.2012, 22:43     Нули в конце записи n! #2
Как вариант можно разложить на множители основание системы счисления, и каждое новое число в подсчете факториала тоже раскладывать. Далее подсчитываем количество каждого интересующего нас простого множителя, и получаем ответ. Возможно, и не самый рациональный путь...
Если нужно, могу написать код.
P.S.:
Цитата Сообщение от SeryZone Посмотреть сообщение
(k>=2>=36).
Что-то тут не так
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
10.07.2012, 23:20  [ТС]     Нули в конце записи n! #3
Цитата Сообщение от UFO94 Посмотреть сообщение
Что-то тут не так
Да, извините, ошибся, вот настоящие ограничения: 2>=k>=5000
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
11.07.2012, 00:39     Нули в конце записи n! #4
Ну, ограничения не принципиально. Код нужен?
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 10:30  [ТС]     Нули в конце записи n! #5
Да. Сколько не думал - не получается.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
11.07.2012, 11:12     Нули в конце записи n! #6
Цитата Сообщение от SeryZone Посмотреть сообщение
Да. Сколько не думал - не получается.
Марсианский факториал?
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 11:23  [ТС]     Нули в конце записи n! #7
Причём тут факториал? Количество нулей важно, а не сам факториал!
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
11.07.2012, 11:42     Нули в конце записи n! #8
Цитата Сообщение от SeryZone Посмотреть сообщение
Причём тут факториал? Количество нулей важно, а не сам факториал!
Просто такая (марсианские факториалы) задача имеет вопрос : Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.
Тогда ладно
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
11.07.2012, 12:15  [ТС]     Нули в конце записи n! #9
Да, да, всё правильно. В начале приводил код с десятичным основанием. Вводятся числа n и k. Ограничения известны.
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
12.07.2012, 02:08     Нули в конце записи n! #10
Ну, возможно, я сейчас напишу не лучший код, но можно так: пусть 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.: Обращайтесь, если будут вопросы по коду.
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
18.07.2012, 14:31  [ТС]     Нули в конце записи n! #11
Да, мало что понятно... Ну что ж, буду разбираться!
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
18.07.2012, 21:35     Нули в конце записи n! #12
Если будете задавать вопросы станет понятнее. Так что именно не понятно?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2012, 22:41     Нули в конце записи n!
Еще ссылки по теме:

"4102" в конце файла при записи C++
C++ Отсортировать массив таким образом, чтобы все нули находились в начале, а единицы — в конце массива
C++ Отсортировать заданную последовательность так, чтобы все нули оказались в конце

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

Или воспользуйтесь поиском по форуму:
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
18.07.2012, 22:41  [ТС]     Нули в конце записи n! #13
Пока разберусь с реализацией, а потом, если что вопросы задам.
Yandex
Объявления
18.07.2012, 22:41     Нули в конце записи n!
Ответ Создать тему
Опции темы

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