Форум программистов, компьютерный форум 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++ Разложение в ряд Помогите пожалуйста Функция Разложение в ряд Область сходимости подробнее

Показать сообщение отдельно
HedgehogLu
 Аватар для HedgehogLu
146 / 67 / 1
Регистрация: 04.09.2013
Сообщений: 250
27.09.2013, 17:34     Быстрый поиск супернатуральных чисел
Готово
блин вроде даже работает и быстро ищет

многие вещи делались для более понятного вида и сокращение циклов (в частности факториал у меня табличный и считается только 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 минут
кстати тут нет функции подсчета затраченного процессорного времени для решения задачи. т.ч. это тоже прикручивать надо, т.к. в условии требуется чтобы прога выполнялась менее секунды.

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