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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ string, invalid null pointer http://www.cyberforum.ru/cpp-beginners/thread621983.html
#include <stdio.h> #include <iostream> #include <string> using namespace std; #define SIZE 450 //--------------------------------------------------------------------------- using namespace std;
C++ Считывание матрицы из файла Есть код, в котором создается динамический массив. Нужно этот массив заполнить из файла. Только размеры зараннее неизвестны. не могу никак с этим разобраться, подскажите пожалуйста #include <iostream> #include <fstream> #include <conio.h> #include <time.h> #include <stdio.h> using namespace std; http://www.cyberforum.ru/cpp-beginners/thread621979.html
Ссылки vs Указатели C++
Почему ссылки считаются более хорошим средством, чем указатели? Ведь если человек будет использовать сторонние классы, он может не заметить, скажем int &val и не будет знать, что передается ссылка, а вовсе не копия. Это может повлечь за собой кучу неприятностей. Даже сам разработчик может спустя время забыть о злополучном знаке &. Так почему ссылки лучше?
return *this; C++
return *this; Возвращает само себя?
C++ Выключение компьютера http://www.cyberforum.ru/cpp-beginners/thread621953.html
Мне нужно выключить компьютер. Операционная система Windows 7. У меня есть вот такой код: HANDLE hToken; TOKEN_PRIVILEGES* NewState; OpenProcessToken (GetCurrentProcess (), TOKEN_ADJUST_PRIVILEGES, &hToken); NewState = (TOKEN_PRIVILEGES*) malloc (sizeof (TOKEN_PRIVILEGES) + sizeof (LUID_AND_ATTRIBUTES)); NewState->PrivilegeCount = 1; LookupPrivilegeValue (NULL, SE_SHUTDOWN_NAME,...
C++ #progma data_seg() , как поместить функцию? #pragma data_seg(".OneSection") char UserName="Ghost Rider"; char Password="12345"; вот так все нормально записывает в секцию а вот если так писать: #pragma data_seg(".OneSection") подробнее

Показать сообщение отдельно
UFO94
 Аватар для UFO94
263 / 252 / 13
Регистрация: 04.04.2012
Сообщений: 546
12.07.2012, 02:08     Нули в конце записи n!
Ну, возможно, я сейчас напишу не лучший код, но можно так: пусть 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.: Обращайтесь, если будут вопросы по коду.
 
Текущее время: 10:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru