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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Найти координаты четвертой вершины параллелограмма http://www.cyberforum.ru/cpp-beginners/thread962988.html
Привет всем. Вот задали совсем простенькую задачку: Известно, что точки с координатами (x1, y1), (x2, y2), (x3, y3) являются тремя вершинами некоторого параллелограмма. Найти координаты четвертой вершины. Все бы хорошо, но я не знаю как ее решить, не как написать код, а саму геометрическую часть, т.е. алгоритм, помогите пожалуйста :)
C++ Чёрный ящик или белый ящик Всем привет. Задали программу написать a + b и сумму вывести в файл, а птом протестировать либо на чёрный ящик, либо на белый ящик. Я лекции прочитал и инфу. в нете, вроде понял , а как писать не знаю. вот код программы подкиньте идеи и код(тестора) , в первый раз на наглядном примере будет легче понять и разобраться спасибо - НАРОД. #include <stdio.h> long a,b; int main(){ ... http://www.cyberforum.ru/cpp-beginners/thread962982.html
C++ Как реализировать заполнение массива квадратами?
Я создал програму которая заполняет двумерный масив символами 35, а потом в рандомных местах создает прямоугольники символами 46, мне нужно чтобы все квадраты были связаны друг с другом линиями из знаков 46, как это осуществить?
Циклы для распечатки чисел C++
Циклы для распечатки чисел. В диалоговом режиме вводится некоторое число N (В диапазоне от 1 до 2000). Программа должна вывести числа, определенные заданием в виде нескольких колонок, выровненных по правому краю. Все числа от 1 до N натуральные. 1) Распечатать числа в диапазоне от 1 до N, у которых самый большой делитель (не равный числу) есть двухзначное число. 2)Распечатать числа в...
C++ перемешать массив http://www.cyberforum.ru/cpp-beginners/thread962963.html
Существует такой алгоритм как random_shuffle. Как сделать чтобы работал данный алгоритм в c++ windows forms?
C++ Разложение в ряд Помогите пожалуйста Функция Разложение в ряд Область сходимости подробнее

Показать сообщение отдельно
Algoritmer
 Аватар для Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 477
Записей в блоге: 1
30.09.2013, 12:00     Быстрый поиск супернатуральных чисел
Ну вот ещё и мой вариант. Написал ещё в субботу, но дома инета нет, пришлось ждать пока на работу выйду, чтоб выложить.
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; //задержка чтоб окно не закрывалось
}
 
Текущее время: 23:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru