Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
#1

Быстрый поиск супернатуральных чисел - C++

26.09.2013, 16:55. Просмотров 1282. Ответов 21
Метки нет (Все метки)

Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно n. Для заданного n выясните, сколько существует супернатуральных чисел.
Технические условия
Входные данные:
Содержит одно целое число n, не превосходящее 2×109.
Выходные данные:
Вывести количество супернатуральных чисел по модулю 101.
Информация о задаче:
Лимит времени: 1 секунда
Лимит памяти: 256 Mб
Пример входных данных 6
Пример выходных данных 3
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2013, 16:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый поиск супернатуральных чисел (C++):

Быстрый поиск совершенных чисел - C++
Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую тему. Напомню, что Доказано, что все четные совершенные...

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый поиск в мапе - C++
Есть мапа вида : std::map<size_t, std::string> Нужно найти элемент меньший или равный элементу из rbf с конца мапы. Есть ли быстрый...

Быстрый поиск элемента - C++
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в...

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector< pair<string, string> > myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

21
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
26.09.2013, 17:25 #2
хм по идее это надо найти на какие цифры от 2 до 9 наше n делится без остатка, определить количество повторений каждого из чисел, а потом высчитать максимальное количество не повторяющихся комбинаций из всех этих цифр. думается так.
Правда вот мне не понятен вопросик с нулем
для нуля получается будет бесконечное множество, т.к. 0*а=0

Добавлено через 7 минут
упс правда вот не знаю еще как решить проблемку с непростыми числами, 4,6,9,8 т.к. они вносят сложности

Добавлено через 4 минуты
Стоп. надо не число комбинаций, а число перестановок считать. И соответственно вычитать количество перестановок для повторяющихся элементов.
И проблем не будет. с простыми числами, а вот с 4,6,8.9 еще не придумал все же
1
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
26.09.2013, 17:30  [ТС] #3
наскалько я понимаю, то 4, 6, 8, 9 разлаживаються дальше на простые как 2*2, 2*3, 2*4 или 2*2*2, 3*3
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
26.09.2013, 18:01 #4
т.е. для представления только простыми числами получается такая вещь.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long count=0;
long num[8];
double res=0;
for(i=2;i<10;i++)
{ 
 num[i-2]=0;
 while((n>1)&&(n%i==0))
  {
   n/=i;
   num[i-2]++;
   count++;
  }
  (num[i-2]>1)?res+=fact(num[i-2]);
}
if (n==1) 
 {
   res=fact(count)-res;
 }
else res=0;
Однако это без учета (непростых чисел)

Добавлено через 2 минуты
Цитата Сообщение от natashka69 Посмотреть сообщение
Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно n.
т.е число 8 можно представить в следующем виде
222
24
42
8
моя же программа разложит только на 222

Добавлено через 6 минут
черт при 222 рез получится 0, но должно быть 1. где то промазал или не учел что-то

Добавлено через 5 минут
хм а если пойти от обратного! сначала делить на непростые числа, а потом остаток на простые.
если получится разложить тогда посчитать результат.
разложить одно непростое на простые и посчитать результат
блин потом надо будет вернуть это раскладывать другое. муторно как то. блин у почему я не силен в комбинаторике

Добавлено через 10 минут
блин может тут какой-то табличный метот используется а не формулами
Помнится есть такой способ нахождения простых чисел путем создания решета где из таблицы чисел вычеркиваются все числа кратные простому после его получения. может и тут так

Добавлено через 44 секунды
как бы было бы хорошо не используйся в задаче числа 4,6,8,9
0
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
26.09.2013, 18:06  [ТС] #5
ето точно
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
26.09.2013, 20:59 #6
Блин пока ехал с работы домой все голову ломал. Да только понял что хорошая штука "разделяй и влавствууй".
Задача то в прочем решена

Создана песочница получения количества чисел получаемых из указанного набора цифр (массив nums), нам остается только для сложных цифр изменять набор в песочнице и добавлять к общей сумме полученный новый набор чисел.

так сделав циклами перебор учитывающий все варианты получим результат. А вот уже имея рабочий код можно искать оптимизацию.
и еще немного не понятно условие
Цитата Сообщение от natashka69 Посмотреть сообщение
Вывести количество супернатуральных чисел по модулю 101.
Если интересно могу ближайшее время написать код решения задачи как он мне видится. но не обещаю положенного быстродействия. (все же лучше чем ничего воообще)
0
Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 484
Записей в блоге: 1
27.09.2013, 09:42 #7
Цитата Сообщение от HedgehogLu Посмотреть сообщение
Если интересно могу ближайшее время написать код решения задачи как он мне видится. но не обещаю положенного быстродействия. (все же лучше чем ничего воообще)
Давай, кто быстрее. Я вчера вечером до пол-12го просидел, уж больно задача интересная
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
27.09.2013, 17:34 #8
Готово
блин вроде даже работает и быстро ищет

многие вещи делались для более понятного вида и сокращение циклов (в частности факториал у меня табличный и считается только 1 раз самый большой заполняющий таблицу)

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <cstdlib>
#include <iostream>
 
using namespace std;
typedef unsigned long DWORD;
 
double *facttable=NULL;
double *facttable2=NULL;
DWORD nums[8];
DWORD countn=0;
double rescomb=0;
 
void initfact(DWORD n)
{
     facttable=new double[n+1];
     facttable2=new double[n+1];
     facttable[0]=1;
     facttable[1]=1;
     facttable2[0]=0;
     facttable2[1]=0;
     for (DWORD i=2;i<=n;i++)
     {
         facttable[i]=facttable[i-1]*i;
         facttable2[i]=facttable[i];
     }
}
 
bool getnums(DWORD n)
{
    rescomb=0;
    countn=0;     
    if (n<2) return 0;
    cout <<"num\tcount"<<endl;;
    for(char i=2,j=0;i<10;i++,j++)
    {
       nums[j]=0;      
       while ((n>1)&&(!(n%i))) 
       {
          n/=i;
          nums[j]++;
          countn++;
       }
       cout<<(char)(48+i)<<"\t"<<nums[j]<<endl;
    }
    cout<<"ostatok = "<<n<<endl;
    if (n!=1) return 0;
    initfact(countn);
    double res=0;
    for (char i=0;i<8;i++) res+=facttable2[nums[i]];
    rescomb=res;
    return 1;
 }
 
void changenums(char inum, long delta)
{
       rescomb-=facttable2[nums[inum]];
       countn+=delta;
       nums[inum]+=delta;
       rescomb+=facttable2[nums[inum]];
}
 
double all4()
{
       double res=0;
       if (nums[0]<2) return res;
       DWORD max4=nums[0]/2;
       for (DWORD i=0;i<max4;i++)
       {
           changenums(0,-2);
           changenums(2,1);
           res+=(facttable[countn]-rescomb);
       }
       changenums(2,(-1)*max4);
       changenums(0,2*max4);
       return res;     
 } 
 
double all8and4()
{
       double res=all4();
       cout<<"4 returned "<<res<<endl;
       if (nums[0]<3) return res;
       DWORD max8=nums[0]/3;
       for (DWORD i=0;i<max8;i++)
       {
           changenums(0,-3);
           changenums(6,1);
           res+=(facttable[countn]-rescomb);
       }
       changenums(6,(-1)*max8);
       changenums(0,3*max8);
       return res;     
 } 
 
double all9and8and4()
{
       double res=all8and4();
       cout<<"84 returned "<<res<<endl;
       if (nums[1]<3) return res;
       DWORD max9=nums[1]/3;
       for (DWORD i=0;i<max9;i++)
       {
           changenums(1,-3);
           changenums(7,1);
           res+=(facttable[countn]-rescomb);
       }
       changenums(7,(-1)*max9);
       changenums(1,3*max9);
       return res;     
 } 
 
double all6and9and8and4()
{
       double res=all9and8and4();
       cout<<"984 returned "<<res<<endl;
       if ((nums[0]<1)||(nums[1]<1)) return res;
       DWORD max6=(nums[0]<nums[1])?nums[0]:nums[1];
       for (DWORD i=0;i<max6;i++)
       {
           changenums(0,-1);
           changenums(1,-1);
           changenums(4,1);
           res+=(facttable[countn]-rescomb);
       }
       changenums(4,(-1)*max6);
       changenums(1,max6);
       changenums(0,max6);
       cout<<"6984 returned "<<res<<endl;
       return res;     
 } 
 
 
 
 
int main(int argc, char *argv[])
{
    DWORD n=0;
    cout<<"n=";
    cin>>n;
    if(getnums(n)) 
    {
         double result=facttable[countn]-rescomb;
         if (result<1) result=1;
         cout<<"rescomb="<<result<<endl;
         result+=all6and9and8and4();
         cout<<n<<" imeet "<<result<<" supernaturalnih chisel"<<endl;;
    }
    else
    {
        cout<<n<<" ne imeet supernaturalnih chisel"<<endl;
    }
    system("PAUSE");
    if (facttable)
    {
       delete[] facttable;
       delete[] facttable2;
    }
    return EXIT_SUCCESS;
}
Algoritmer я быстрее

Добавлено через 5 минут
Важная заметка. В случае когда большое количество повторяющихся цифр и соответственно большое число перестановок которые не меняют числа програма может давать погрешность, что связанно с точностью типа дабл.
Для избежания постоянного цикличного пересчета количества ненужных перестановок ввел функция которая рассчитывает изменения количества бесполезных перестановок в соответствии с изменением количественного показателя одной цифры. Осуществляя относительные изменения, вот тут и может быть накопительная ошибка, но думаю данный случай достаточно редок и является допустимым

Добавлено через 1 минуту
natashka69, смотри проверяй пользуйся комментариев не ставил, чтобы хоть при разборе кода алгоритм выстроился и не даром для головы прошел код

Добавлено через 16 минут
кстати тут нет функции подсчета затраченного процессорного времени для решения задачи. т.ч. это тоже прикручивать надо, т.к. в условии требуется чтобы прога выполнялась менее секунды.

Хотя по мне так это не точное условие, т.к. на моей домашней оно считает мигом, но не факт что она быстро будет считать на дохленькой машинке, которая еще и сама по себе тормозит . Т.ч. без хардварных характеристик требовать оптимальную работу по времени порой глупо
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
27.09.2013, 22:37 #9
решение, которое проходит все тесты вот тут: http://www.e-olimp.com/problems/6082
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
#include <cstdio>
#include <map>
using namespace std;
 
typedef char byte;
typedef map< int, byte > mymap;
typedef pair< int, byte > mypair;
 
mymap m;
 
byte calc( int n )
{
    if ( n == 1 ) return 1;
    if ( m.find( n ) != m.end() ) return m[ n ];
 
    int res = 0;
 
    for ( int i = 2, x; i <= 9; ++i )
    {
        x = n / i;
        if ( x * i == n )
        {
            if ( m.find( x ) != m.end() ) res += m[ x ];
            else res += calc( x );
        }
    }
    m.insert( mypair( n, res % 101 ) );
    return m[ n ];
}
 
int main()
{
    int n;
 
    scanf( "%d", &n );
    if ( n == 1 ) printf( "%d\n", 0 );
    else printf( "%d\n", calc( n ) );
 
    return 0;
}
и не спрашивайте почему при сохранении промежуточных результатов map не разрастается до гигабайта (например при n=230), сам не знаю

HedgehogLu, для n=24 количество супернатуральных чисел равно 17, а твоя прога выдает 30
0
zer0mail
27.09.2013, 23:13
  #10

Не по теме:

Имхо, просить решить олимпидные задачи - это как просить изготовить инструмент для взлома. В результате конкурс пройдет не тот, кто сам решил 5 задач, а тот, кто на форумах выклянчил решение 7 задач Вот только в отличии от взломщика, плоды взлома со временем обязательно вылезут боком.

И еще интелектуальный труд составителей таких задач уничтожается

2
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
28.09.2013, 11:55 #11
мдя алгоритмическая ошибочка есть

Добавлено через 1 час 52 минуты
Да были недочеты, т.к. не правильно вычитал количество комбинаций (изначально расчет не правильный был, т.к. влияние повторов разных чисел не ссумируется а у множается, более того забыл влючать повторные расчеты прошлых комбинаций при измененни набора цифр при 8,9 и 6.
Вроде все надочеты исправил

(не пишите программы по ночам )
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <cstdlib>
#include <iostream>
 
using namespace std;
typedef unsigned long DWORD;
 
double *facttable=NULL;
DWORD nums[8];
DWORD countn=0;
double rescomb=0;
 
void initfact(DWORD n)
{
     facttable=new double[n+1];
     facttable[0]=1;
     facttable[1]=1;
     for (DWORD i=2;i<=n;i++) facttable[i]=facttable[i-1]*i;
}
 
bool getnums(DWORD n)
{
    rescomb=0;
    countn=0;     
    if (n<2) return 0;
    cout <<"num\tcount"<<endl;;
    for(char i=2,j=0;i<10;i++,j++)
    {
       nums[j]=0;      
       while ((n>1)&&(!(n%i))) 
       {
          n/=i;
          nums[j]++;
          countn++;
       }
       cout<<(char)(48+i)<<"\t"<<nums[j]<<endl;
    }
    cout<<"ostatok = "<<n<<endl;
    if (n!=1) return 0;
    initfact(countn);
    double res=1;
    for (char i=0;i<8;i++) res*=facttable[nums[i]];
    rescomb=res;
    return 1;
 }
 
void changenums(char inum, long delta)
{
       rescomb/=facttable[nums[inum]];
       countn+=delta;
       nums[inum]+=delta;
       rescomb*=facttable[nums[inum]];
}
 
double all4()
{
       double res=0;
       if (nums[0]<2) return res;
       DWORD max4=nums[0]/2;
       for (DWORD i=0;i<max4;i++)
       {
           changenums(0,-2);
           changenums(2,1);
           if(rescomb)res+=(facttable[countn]/rescomb);
       }
       changenums(2,(-1)*max4);
       changenums(0,2*max4);
       return res;     
 } 
 
double all8and4()
{
       double res=all4();
       cout<<"4 returned "<<res<<endl;
       if (nums[0]<3) return res;
       DWORD max8=nums[0]/3;
       for (DWORD i=0;i<max8;i++)
       {
           changenums(0,-3);
           changenums(6,1);
           if(rescomb)res+=(facttable[countn]/rescomb);
           res+=all4();
       }
       changenums(6,(-1)*max8);
       changenums(0,3*max8);
       return res;     
 } 
 
double all9and8and4()
{
       double res=all8and4();
       cout<<"84 returned "<<res<<endl;
       if (nums[1]<3) return res;
       DWORD max9=nums[1]/3;
       for (DWORD i=0;i<max9;i++)
       {
           changenums(1,-3);
           changenums(7,1);
           if(rescomb)res+=(facttable[countn]/rescomb);
           res+=all8and4();
       }
       changenums(7,(-1)*max9);
       changenums(1,3*max9);
       return res;     
 } 
 
double all6and9and8and4()
{
       double res=all9and8and4();
       cout<<"984 returned "<<res<<endl;
       if ((nums[0]<1)||(nums[1]<1)) return res;
       DWORD max6=(nums[0]<nums[1])?nums[0]:nums[1];
       for (DWORD i=0;i<max6;i++)
       {
           changenums(0,-1);
           changenums(1,-1);
           changenums(4,1);
           if(rescomb)res+=(facttable[countn]/rescomb);
           res+=all9and8and4();
       }
       changenums(4,(-1)*max6);
       changenums(1,max6);
       changenums(0,max6);
       cout<<"6984 returned "<<res<<endl;
       return res;     
 } 
 
 
 
 
int main(int argc, char *argv[])
{
    DWORD n=0;
    cout<<"n=";
    cin>>n;
    if(getnums(n)) 
    {
         double result=facttable[countn];          
         cout<<"rescomb="<<rescomb<<endl;
         if(rescomb)result/=rescomb;
         if (result<1) result=1;
         cout<<"result="<<result<<endl;
         result+=all6and9and8and4();
         cout<<n<<" imeet "<<result<<" supernaturalnih chisel"<<endl;;
    }
    else
    {
        cout<<n<<" ne imeet supernaturalnih chisel"<<endl;
    }
    system("PAUSE");
    if (facttable)
    {
       delete[] facttable;
    }
    return EXIT_SUCCESS;
}
1
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
29.09.2013, 15:23  [ТС] #12
спасибо)
0
Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 484
Записей в блоге: 1
30.09.2013, 12:00 #13
Ну вот ещё и мой вариант. Написал ещё в субботу, но дома инета нет, пришлось ждать пока на работу выйду, чтоб выложить.
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <iostream>
using namespace std;
 
struct NaborElem
{
    int value;
    NaborElem *Next;
};
class NaborList
{
private:
    int childNabSize;   
public:
    NaborElem *FirElem;
    NaborList **childNabors; //array
    int countElems;
    NaborList()
    {
        FirElem=NULL;
        childNabors=NULL;
        countElems=0;
        childNabSize=0;
    }
    void addChildNabor(NaborList *nabor)
    {
        if(!childNabors)
        {
            childNabSize=1;
            childNabors=new NaborList*[1];
            childNabors[0]=nabor;
        }
        else
        {
            childNabSize++;
            NaborList **chnabor2=new NaborList*[childNabSize];
            for(int i=0;i<childNabSize-1;i++) chnabor2[i]=childNabors[i];
            chnabor2[childNabSize-1]=nabor;
            delete []childNabors;
            childNabors=chnabor2;
        }
    }
    int* NaborToArray()
    {       
        if(!FirElem) return NULL;
        int *nbArray=new int[countElems];
        int i=0;
        NaborElem *T=FirElem;
        while(T && i<countElems)
        {
            nbArray[i]=T->value;
            i++;
            T=T->Next;
        }
        return nbArray;
    }
    void loadFromArray(int *arr, int arrCount)
    {
        FirElem=new NaborElem;
        FirElem->value=arr[0];
        FirElem->Next=NULL;
        NaborElem *T=FirElem;
        countElems=1;
        for(int i=1;i<arrCount;i++)
        {
            if(arr[i]==0) continue;
            T->Next=new NaborElem;
            T=T->Next;
            T->value=arr[i];
            T->Next=NULL;
            countElems++;
        }
    }
    int getChildNaborCount()//только прямые потомки
    {
        return childNabSize; 
    }
    
}*nabors;
int allNaborsCount;
NaborList *tmpNabor;
void getAllChildNabors(NaborList *teknabor)//обойти дерево и записать всех как детей первого уровня в tmpNabor
{
    tmpNabor->addChildNabor(teknabor);
    int chCount=teknabor->getChildNaborCount();
    for(int i=0;i<chCount;i++) getAllChildNabors(teknabor->childNabors[i]); 
}
bool arrayCmp(int *arr1, int *arr2, int countelem) //если совпадают вернет true
{   
    for(int i=0;i<countelem;i++)
    {
        if(arr1[i]!=arr2[i]) return false;
    }
    return true;
}
NaborList *findSimpleNabor(int n)
{
    int devs[]={2,3,5,7};
    NaborList *simpleNabor=new NaborList;
    simpleNabor->childNabors=NULL;
    simpleNabor->countElems=0;
    simpleNabor->FirElem=NULL;
    NaborElem *T;
    for(int i=0;i<=3;i++)
    {
        while(n%devs[i]==0)
        {
            if(simpleNabor->FirElem)
            {
                T->Next=new NaborElem;
                T=T->Next;
            }
            else
            {
                simpleNabor->FirElem=new NaborElem;
                T=simpleNabor->FirElem;
            }
            T->Next=NULL;
            T->value=devs[i];
            (simpleNabor->countElems)++;
            n/=devs[i];
        }   
    }
    if(n>1) return NULL; //неверное значение n
    return simpleNabor; 
}
NaborElem* sortNabor(NaborElem *Nabor)
{
    NaborElem *nab2, *T2, *T=Nabor;
    nab2=Nabor;
    T=T->Next;
    nab2->Next=NULL;
    while(T)
    {
        T2=nab2;
        if(T->value<=T2->value)
        {
            NaborElem *T3=T->Next;
            T->Next=T2;
            nab2=T;
            T=T3;
            continue;
        }
        while(T2->Next && T->value>T2->Next->value) T2=T2->Next;
        NaborElem *T3=T2->Next;
        T2->Next=T;
        T=T->Next;
        T2->Next->Next=T3;
    }
    return nab2;
}
void addNaborElem(NaborElem **Nabor, NaborElem *addElem)
{
    if(!(*Nabor)) (*Nabor)=addElem;
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=addElem;
    }
}
void addNaborElem(NaborElem **Nabor, int elem)
{
    if(!(*Nabor)) 
    {
        (*Nabor)=new NaborElem;
        (*Nabor)->value=elem;
        (*Nabor)->Next=NULL;
    }
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=new NaborElem;
        T->Next->value=elem;
        T->Next->Next=NULL;
    }
}
 void insertNabor(NaborElem *PrevElem, NaborElem *insNabor)//нельзя вставить в начало
 {
     NaborElem *Next=PrevElem->Next;
     PrevElem->Next=insNabor;
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=Next;
 }
 NaborList *cloneNabor(NaborList *source)
 {
     NaborList *dest=new NaborList;
     //dest->FirElem=new NaborElem;
     NaborElem *T=source->FirElem;
     while(T)
     {
         addNaborElem(&(dest->FirElem),T->value);
         T=T->Next;
     }
     return dest;
 }
 void insertNaborPrevFirst(NaborElem *First, NaborElem *insNabor)
 {
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=First;
 }
void findNabors(NaborList *teknabor)
{
    allNaborsCount++;
    if(teknabor->countElems>1)
    {
        int *ar=teknabor->NaborToArray();
        for(int i=0;i<(teknabor->countElems-1);i++)
            for(int j=i+1;j<(teknabor->countElems);j++)
            {
                if(ar[i]*ar[j]<=9)
                {
                    ar[i]*=ar[j];
                    ar[j]=0; //будет пропущен при преобразовании
                    NaborList *newNabor=new NaborList;
                    newNabor->loadFromArray(ar, teknabor->countElems); // вот здесь пропускаем j
                    newNabor->FirElem=sortNabor(newNabor->FirElem);
                    teknabor->addChildNabor(newNabor);
                    findNabors(newNabor);  //строим дерево
                    delete []ar;
                    ar=teknabor->NaborToArray(); //обновить массив для последующего поиска
                }
            }       
    }
}
//количество перестановок для набора
long long factorial(int i)
{
    if(i==0 || i==1) return 1;
    long long res=1;
    for(int k=2;k<=i;k++) res*=k;
    return res;
}
long long PCount(int *nabArray, int len)
{
    int *repeatcount=new int[10]; //0,1 -not use
    for(int i=0;i<=9;i++) repeatcount[i]=0;
    for(int i=0;i<len;i++)
    {
        repeatcount[nabArray[i]]++;
    }
    long long res=factorial(len);
    for(int i=0;i<=9;i++) res/=factorial(repeatcount[i]);
    delete []repeatcount;
    return res;
}
void main()
{
    cout<<"input super natural proizv sign: ";
    int n;  
    for(;;)
    {
        cin>>n;
        allNaborsCount=0;
        nabors=findSimpleNabor(n); //здесь ищем набор, состоящий только из простых чисел
        if(!nabors)
        {
            cout<<"no correct value, input super natural proizv sign again: ";          
        }
        else break;
    }
    findNabors(nabors); //строим дерево
    tmpNabor=new NaborList;
    getAllChildNabors(nabors); //преобразуем дерево в массив
    //преобразуем массив
    int nbCount=tmpNabor->getChildNaborCount();
    int **allNabors=new int*[nbCount];
    int *allNaborsLens=new int[nbCount];
    for(int i=0;i<nbCount;i++)
    {
        allNabors[i]=tmpNabor->childNabors[i]->NaborToArray();
        allNaborsLens[i]=tmpNabor->childNabors[i]->countElems;
    }
    
 
    //найдем и удалим дубликаты
    int realCount=nbCount;
    for(int i=0;i<realCount;i++)
    {
        for(int j=i+1;j<realCount;j++)
        {
            if(allNaborsLens[i]==allNaborsLens[j] && arrayCmp(allNabors[i],allNabors[j],allNaborsLens[i]))
            {
                delete [](allNabors[j]);
                for(int k=j;k<realCount-1;k++)
                {
                    allNabors[k]=allNabors[k+1];
                    allNaborsLens[k]=allNaborsLens[k+1];
                }
                allNabors[realCount-1]=NULL;
                realCount--;
                j--; //c учетом удаленой строки
            }
        }
    }
    //подсчитаем колиечство повторений в наборах
    long long pcnt=0;
    for(int i=0;i<realCount;i++) pcnt+=PCount(allNabors[i], allNaborsLens[i]);
    cout<<"super natural count: "<<pcnt<<" \nDo you want to see nabor? (y/n): ";
    char a=getchar();
    cin>>a; 
    //n=getchar();
    if(a=='y' || a=='Y')
    {
        for(int i=0;i<realCount;i++)
        {
            for(int j=0;j<allNaborsLens[i];j++)
            {
                cout<<allNabors[i][j]<<" ";
            }
            cout<<'\n';
        }
    }
    cin>>n; //задержка чтоб окно не закрывалось
}
Добавлено через 13 минут
Ошибся когда выкладывал. Вот так правильней:
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <iostream>
using namespace std;
 
struct NaborElem
{
    int value;
    NaborElem *Next;
};
class NaborList
{
private:
    int childNabSize;   
public:
    NaborElem *FirElem;
    NaborList **childNabors; //array
    int countElems;
    NaborList()
    {
        FirElem=NULL;
        childNabors=NULL;
        countElems=0;
        childNabSize=0;
    }
    void addChildNabor(NaborList *nabor)
    {
        if(!childNabors)
        {
            childNabSize=1;
            childNabors=new NaborList*[1];
            childNabors[0]=nabor;
        }
        else
        {
            childNabSize++;
            NaborList **chnabor2=new NaborList*[childNabSize];
            for(int i=0;i<childNabSize-1;i++) chnabor2[i]=childNabors[i];
            chnabor2[childNabSize-1]=nabor;
            delete []childNabors;
            childNabors=chnabor2;
        }
    }
    int* NaborToArray()
    {       
        if(!FirElem) return NULL;
        int *nbArray=new int[countElems];
        int i=0;
        NaborElem *T=FirElem;
        while(T && i<countElems)
        {
            nbArray[i]=T->value;
            i++;
            T=T->Next;
        }
        return nbArray;
    }
    void loadFromArray(int *arr, int arrCount)
    {
        FirElem=new NaborElem;
        FirElem->value=arr[0];
        FirElem->Next=NULL;
        NaborElem *T=FirElem;
        countElems=1;
        for(int i=1;i<arrCount;i++)
        {
            if(arr[i]==0) continue;
            T->Next=new NaborElem;
            T=T->Next;
            T->value=arr[i];
            T->Next=NULL;
            countElems++;
        }
    }
    int getChildNaborCount()//только прямые потомки
    {
        return childNabSize; 
    }
    
}*nabors;
int allNaborsCount;
NaborList *tmpNabor;
void getAllChildNabors(NaborList *teknabor)//обойти дерево и записать всех как детей первого уровня в tmpNabor
{
    tmpNabor->addChildNabor(teknabor);
    int chCount=teknabor->getChildNaborCount();
    for(int i=0;i<chCount;i++) getAllChildNabors(teknabor->childNabors[i]); 
}
bool arrayCmp(int *arr1, int *arr2, int countelem) //если совпадают вернет true
{   
    for(int i=0;i<countelem;i++)
    {
        if(arr1[i]!=arr2[i]) return false;
    }
    return true;
}
NaborList *findSimpleNabor(int n)
{
    int devs[]={2,3,5,7};
    NaborList *simpleNabor=new NaborList;
    simpleNabor->childNabors=NULL;
    simpleNabor->countElems=0;
    simpleNabor->FirElem=NULL;
    NaborElem *T;
    for(int i=0;i<=3;i++)
    {
        while(n%devs[i]==0)
        {
            if(simpleNabor->FirElem)
            {
                T->Next=new NaborElem;
                T=T->Next;
            }
            else
            {
                simpleNabor->FirElem=new NaborElem;
                T=simpleNabor->FirElem;
            }
            T->Next=NULL;
            T->value=devs[i];
            (simpleNabor->countElems)++;
            n/=devs[i];
        }   
    }
    if(n>1) return NULL; //неверное значение n
    return simpleNabor; 
}
NaborElem* sortNabor(NaborElem *Nabor)
{
    NaborElem *nab2, *T2, *T=Nabor;
    nab2=Nabor;
    T=T->Next;
    nab2->Next=NULL;
    while(T)
    {
        T2=nab2;
        if(T->value<=T2->value)
        {
            NaborElem *T3=T->Next;
            T->Next=T2;
            nab2=T;
            T=T3;
            continue;
        }
        while(T2->Next && T->value>T2->Next->value) T2=T2->Next;
        NaborElem *T3=T2->Next;
        T2->Next=T;
        T=T->Next;
        T2->Next->Next=T3;
    }
    return nab2;
}
void addNaborElem(NaborElem **Nabor, NaborElem *addElem)
{
    if(!(*Nabor)) (*Nabor)=addElem;
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=addElem;
    }
}
void addNaborElem(NaborElem **Nabor, int elem)
{
    if(!(*Nabor)) 
    {
        (*Nabor)=new NaborElem;
        (*Nabor)->value=elem;
        (*Nabor)->Next=NULL;
    }
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=new NaborElem;
        T->Next->value=elem;
        T->Next->Next=NULL;
    }
}
 void insertNabor(NaborElem *PrevElem, NaborElem *insNabor)//нельзя вставить в начало
 {
     NaborElem *Next=PrevElem->Next;
     PrevElem->Next=insNabor;
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=Next;
 }
 NaborList *cloneNabor(NaborList *source)
 {
     NaborList *dest=new NaborList;
     //dest->FirElem=new NaborElem;
     NaborElem *T=source->FirElem;
     while(T)
     {
         addNaborElem(&(dest->FirElem),T->value);
         T=T->Next;
     }
     return dest;
 }
 void insertNaborPrevFirst(NaborElem *First, NaborElem *insNabor)
 {
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=First;
 }
void findNabors(NaborList *teknabor)
{
    allNaborsCount++;
    if(teknabor->countElems>1)
    {
        int *ar=teknabor->NaborToArray();
        for(int i=0;i<(teknabor->countElems-1);i++)
            for(int j=i+1;j<(teknabor->countElems);j++)
            {
                if(ar[i]*ar[j]<=9)
                {
                    ar[i]*=ar[j];
                    ar[j]=0; //будет пропущен при преобразовании
                    NaborList *newNabor=new NaborList;
                    newNabor->loadFromArray(ar, teknabor->countElems); // вот здесь пропускаем j
                    newNabor->FirElem=sortNabor(newNabor->FirElem);
                    teknabor->addChildNabor(newNabor);
                    findNabors(newNabor);  //строим дерево
                    delete []ar;
                    ar=teknabor->NaborToArray(); //обновить массив для последующего поиска
                }
            }       
    }
}
//количество перестановок для набора
long long factorial(int i)
{
    if(i==0 || i==1) return 1;
    long long res=1;
    for(int k=2;k<=i;k++) res*=k;
    return res;
}
long long PCount(int *nabArray, int len)
{
    int *repeatcount=new int[10]; //0,1 -not use
    for(int i=0;i<=9;i++) repeatcount[i]=0;
    for(int i=0;i<len;i++)
    {
        repeatcount[nabArray[i]]++;
    }
    long long res=factorial(len);
    for(int i=0;i<=9;i++) res/=factorial(repeatcount[i]);
    delete []repeatcount;
    return res;
}
void main()
{
    cout<<"input super natural proizv sign: ";
    int n;  
    for(;;)
    {
        cin>>n;
        allNaborsCount=0;
        nabors=findSimpleNabor(n); //здесь ищем набор, состоящий только из простых чисел
        if(!nabors)
        {
            cout<<"no correct value, input super natural proizv sign again: ";          
        }
        else break;
    }
    findNabors(nabors); //строим дерево
    tmpNabor=new NaborList;
    getAllChildNabors(nabors); //преобразуем дерево в массив
    //преобразуем массив
    int nbCount=tmpNabor->getChildNaborCount();
    int **allNabors=new int*[nbCount];
    int *allNaborsLens=new int[nbCount];
    for(int i=0;i<nbCount;i++)
    {
        allNabors[i]=tmpNabor->childNabors[i]->NaborToArray();
        allNaborsLens[i]=tmpNabor->childNabors[i]->countElems;
    }
    
 
    //найдем и удалим дубликаты
    int realCount=nbCount;
    for(int i=0;i<realCount;i++)
    {
        for(int j=i+1;j<realCount;j++)
        {
            if(allNaborsLens[i]==allNaborsLens[j] && arrayCmp(allNabors[i],allNabors[j],allNaborsLens[i]))
            {
                delete [](allNabors[j]);
                for(int k=j;k<realCount-1;k++)
                {
                    allNabors[k]=allNabors[k+1];
                    allNaborsLens[k]=allNaborsLens[k+1];
                }
                allNabors[realCount-1]=NULL;
                realCount--;
                j--; //c учетом удаленой строки
            }
        }
    }
    //подсчитаем колиечство повторений в наборах
    long long pcnt=0;
    for(int i=0;i<realCount;i++) pcnt+=PCount(allNabors[i], allNaborsLens[i]);
    cout<<"super natural count: "<<pcnt<<" \nDo you want to see nabor? (y/n): ";
    char a=getchar();    
    if(a=='y' || a=='Y')
    {
        for(int i=0;i<realCount;i++)
        {
            for(int j=0;j<allNaborsLens[i];j++)
            {
                cout<<allNabors[i][j]<<" ";
            }
            cout<<'\n';
        }
    }
    cin>>n; //задержка чтоб окно не закрывалось
}
Добавлено через 3 минуты
HedgehogLu, c initfact хорошая идея. Сразу не подумал о том, чтоб вычислить факториалы 1 раз

Добавлено через 1 час 51 минуту
HedgehogLu, проверил работоспособность вашего кода. Для n=144 ваша программа выдает результат:
n=144
num count
2 4
3 2
4 0
5 0
6 0
7 0
8 0
9 0
ostatok = 1
rescomb=48
result=15
4 returned 36
84 returned 48
984 returned 48
4 returned 24
84 returned 30
4 returned 3
84 returned 3
6984 returned 107
144 imeet 122 supernaturalnih chisel

Я так понимаю ответ 122, а должен быть 148. Код не рабочий!!!

Добавлено через 2 минуты
В моем сообщении (в последнем коде) должно быть вместо 302-й строки
C++
1
2
char a;
cin>>a;
Добавлено через 8 минут
ya_noob, твой код работает правильно. Помоги понять, как он работает

Добавлено через 2 минуты
Ну и чтоб уж польностью соответствовал заданию, добавлю и я вывод по модулю 101:
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
#include <iostream>
using namespace std;
 
struct NaborElem
{
    int value;
    NaborElem *Next;
};
class NaborList
{
private:
    int childNabSize;   
public:
    NaborElem *FirElem;
    NaborList **childNabors; //array
    int countElems;
    NaborList()
    {
        FirElem=NULL;
        childNabors=NULL;
        countElems=0;
        childNabSize=0;
    }
    void addChildNabor(NaborList *nabor)
    {
        if(!childNabors)
        {
            childNabSize=1;
            childNabors=new NaborList*[1];
            childNabors[0]=nabor;
        }
        else
        {
            childNabSize++;
            NaborList **chnabor2=new NaborList*[childNabSize];
            for(int i=0;i<childNabSize-1;i++) chnabor2[i]=childNabors[i];
            chnabor2[childNabSize-1]=nabor;
            delete []childNabors;
            childNabors=chnabor2;
        }
    }
    int* NaborToArray()
    {       
        if(!FirElem) return NULL;
        int *nbArray=new int[countElems];
        int i=0;
        NaborElem *T=FirElem;
        while(T && i<countElems)
        {
            nbArray[i]=T->value;
            i++;
            T=T->Next;
        }
        return nbArray;
    }
    void loadFromArray(int *arr, int arrCount)
    {
        FirElem=new NaborElem;
        FirElem->value=arr[0];
        FirElem->Next=NULL;
        NaborElem *T=FirElem;
        countElems=1;
        for(int i=1;i<arrCount;i++)
        {
            if(arr[i]==0) continue;
            T->Next=new NaborElem;
            T=T->Next;
            T->value=arr[i];
            T->Next=NULL;
            countElems++;
        }
    }
    int getChildNaborCount()//только прямые потомки
    {
        return childNabSize; 
    }
    
}*nabors;
int allNaborsCount;
NaborList *tmpNabor;
void getAllChildNabors(NaborList *teknabor)//обойти дерево и записать всех как детей первого уровня в tmpNabor
{
    tmpNabor->addChildNabor(teknabor);
    int chCount=teknabor->getChildNaborCount();
    for(int i=0;i<chCount;i++) getAllChildNabors(teknabor->childNabors[i]); 
}
bool arrayCmp(int *arr1, int *arr2, int countelem) //если совпадают вернет true
{   
    for(int i=0;i<countelem;i++)
    {
        if(arr1[i]!=arr2[i]) return false;
    }
    return true;
}
NaborList *findSimpleNabor(int n)
{
    int devs[]={2,3,5,7};
    NaborList *simpleNabor=new NaborList;
    simpleNabor->childNabors=NULL;
    simpleNabor->countElems=0;
    simpleNabor->FirElem=NULL;
    NaborElem *T;
    for(int i=0;i<=3;i++)
    {
        while(n%devs[i]==0)
        {
            if(simpleNabor->FirElem)
            {
                T->Next=new NaborElem;
                T=T->Next;
            }
            else
            {
                simpleNabor->FirElem=new NaborElem;
                T=simpleNabor->FirElem;
            }
            T->Next=NULL;
            T->value=devs[i];
            (simpleNabor->countElems)++;
            n/=devs[i];
        }   
    }
    if(n>1) return NULL; //неверное значение n
    return simpleNabor; 
}
NaborElem* sortNabor(NaborElem *Nabor)
{
    NaborElem *nab2, *T2, *T=Nabor;
    nab2=Nabor;
    T=T->Next;
    nab2->Next=NULL;
    while(T)
    {
        T2=nab2;
        if(T->value<=T2->value)
        {
            NaborElem *T3=T->Next;
            T->Next=T2;
            nab2=T;
            T=T3;
            continue;
        }
        while(T2->Next && T->value>T2->Next->value) T2=T2->Next;
        NaborElem *T3=T2->Next;
        T2->Next=T;
        T=T->Next;
        T2->Next->Next=T3;
    }
    return nab2;
}
void addNaborElem(NaborElem **Nabor, NaborElem *addElem)
{
    if(!(*Nabor)) (*Nabor)=addElem;
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=addElem;
    }
}
void addNaborElem(NaborElem **Nabor, int elem)
{
    if(!(*Nabor)) 
    {
        (*Nabor)=new NaborElem;
        (*Nabor)->value=elem;
        (*Nabor)->Next=NULL;
    }
    else
    {
        NaborElem *T=(*Nabor);
        while(T->Next) T=T->Next;
        T->Next=new NaborElem;
        T->Next->value=elem;
        T->Next->Next=NULL;
    }
}
 void insertNabor(NaborElem *PrevElem, NaborElem *insNabor)//нельзя вставить в начало
 {
     NaborElem *Next=PrevElem->Next;
     PrevElem->Next=insNabor;
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=Next;
 }
 NaborList *cloneNabor(NaborList *source)
 {
     NaborList *dest=new NaborList;
     //dest->FirElem=new NaborElem;
     NaborElem *T=source->FirElem;
     while(T)
     {
         addNaborElem(&(dest->FirElem),T->value);
         T=T->Next;
     }
     return dest;
 }
 void insertNaborPrevFirst(NaborElem *First, NaborElem *insNabor)
 {
     NaborElem *T=insNabor;
     while(T->Next) T=T->Next;
     T->Next=First;
 }
void findNabors(NaborList *teknabor)
{
    allNaborsCount++;
    if(teknabor->countElems>1)
    {
        int *ar=teknabor->NaborToArray();
        for(int i=0;i<(teknabor->countElems-1);i++)
            for(int j=i+1;j<(teknabor->countElems);j++)
            {
                if(ar[i]*ar[j]<=9)
                {
                    ar[i]*=ar[j];
                    ar[j]=0; //будет пропущен при преобразовании
                    NaborList *newNabor=new NaborList;
                    newNabor->loadFromArray(ar, teknabor->countElems); // вот здесь пропускаем j
                    newNabor->FirElem=sortNabor(newNabor->FirElem);
                    teknabor->addChildNabor(newNabor);
                    findNabors(newNabor);  //строим дерево
                    delete []ar;
                    ar=teknabor->NaborToArray(); //обновить массив для последующего поиска
                }
            }       
    }
}
//количество перестановок для набора
long long factorial(int i)
{
    if(i==0 || i==1) return 1;
    long long res=1;
    for(int k=2;k<=i;k++) res*=k;
    return res;
}
long long PCount(int *nabArray, int len)
{
    int *repeatcount=new int[10]; //0,1 -not use
    for(int i=0;i<=9;i++) repeatcount[i]=0;
    for(int i=0;i<len;i++)
    {
        repeatcount[nabArray[i]]++;
    }
    long long res=factorial(len);
    for(int i=0;i<=9;i++) res/=factorial(repeatcount[i]);
    delete []repeatcount;
    return res;
}
void main()
{
    cout<<"input super natural proizv sign: ";
    int n;  
    for(;;)
    {
        cin>>n;
        allNaborsCount=0;
        nabors=findSimpleNabor(n); //здесь ищем набор, состоящий только из простых чисел
        if(!nabors)
        {
            cout<<"no correct value, input super natural proizv sign again: ";          
        }
        else break;
    }
    findNabors(nabors); //строим дерево
    tmpNabor=new NaborList;
    getAllChildNabors(nabors); //преобразуем дерево в массив
    //преобразуем массив
    int nbCount=tmpNabor->getChildNaborCount();
    int **allNabors=new int*[nbCount];
    int *allNaborsLens=new int[nbCount];
    for(int i=0;i<nbCount;i++)
    {
        allNabors[i]=tmpNabor->childNabors[i]->NaborToArray();
        allNaborsLens[i]=tmpNabor->childNabors[i]->countElems;
    }
    
 
    //найдем и удалим дубликаты
    int realCount=nbCount;
    for(int i=0;i<realCount;i++)
    {
        for(int j=i+1;j<realCount;j++)
        {
            if(allNaborsLens[i]==allNaborsLens[j] && arrayCmp(allNabors[i],allNabors[j],allNaborsLens[i]))
            {
                delete [](allNabors[j]);
                for(int k=j;k<realCount-1;k++)
                {
                    allNabors[k]=allNabors[k+1];
                    allNaborsLens[k]=allNaborsLens[k+1];
                }
                allNabors[realCount-1]=NULL;
                realCount--;
                j--; //c учетом удаленой строки
            }
        }
    }
    //подсчитаем колиечство повторений в наборах
    long long pcnt=0;
    for(int i=0;i<realCount;i++) pcnt+=PCount(allNabors[i], allNaborsLens[i]);
    cout<<"super natural count: "<<(pcnt%101)<<" \nDo you want to see nabor? (y/n): ";
    char a;    
    cin>>a;
    if(a=='y' || a=='Y')
    {
        for(int i=0;i<realCount;i++)
        {
            for(int j=0;j<allNaborsLens[i];j++)
            {
                cout<<allNabors[i][j]<<" ";
            }
            cout<<'\n';
        }
    }
    cin>>n; //задержка чтоб окно не закрывалось
}
1
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
30.09.2013, 15:46 #14
Algoritmer, Блин ну говорилось же не пиши ночью если отладку делать, то делать качественно

Вот скажите с каких пор 3*3*3=9? Опять попался на том, что суммировал а не умножал.
Алгоритм верный а попался 2 раза просто на том что спутал операции суммирования и умножения.

Приведу кусок который исправить надобно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double all9and8and4()
{
       double res=all8and4();
       if (nums[1]<2) return res;
       DWORD max9=nums[1]/2;
       for (DWORD i=0;i<max9;i++)
       {
           changenums(1,-2);
           changenums(7,1);
           if(rescomb)res+=(facttable[countn]/rescomb);
           res+=all8and4();
       }
       changenums(7,(-1)*max9);
       changenums(1,2*max9);
       cout<<"984 returned "<<res<<endl;
       return res;     
 }
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
30.09.2013, 19:45 #15
Algoritmer, ваш код крашится у меня при больших значениях (типа 2*10^9) (много памяти ест, в условии сказано ограничение памяти в 256 мб).
Цитата Сообщение от Algoritmer Посмотреть сообщение
Помоги понять, как он работает
всё просто! перебираем все возможные комбинации цифр, произведение которых равно данному + динамическое программирование, чтобы не пересчитывать комбинации цифр с одинаковым произведением (иначе будет экспоненциальная сложность)
0
30.09.2013, 19:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.09.2013, 19:45
Привет! Вот еще темы с ответами:

Быстрый поиск по полям в коллекции - C++
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый поиск первого элемента (может потом множества элементов) по...

Быстрый поиск ip адреса в текстовом файле - C++
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300...

Быстрый поиск наиболее близких вершин графа - C++
Всем привет, у меня имеется некая задача и её суть состоит в том, что мне нужно найти расстояние между двумя наиболее близкими вершинами...

Подскажите быстрый поиск количества интервалов в отрезке - C++
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на которое делится отрезок x+dx массивом H. Наверняка с такой...


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

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

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