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

Лотерея - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перестановка столбцов матрицы http://www.cyberforum.ru/cpp-beginners/thread1010923.html
Помогите разобраться, суть задачи: Дана целочисленная матрица размера 6х9. Найти матрицу, получающуюся из данной: перестановкой строк - первой с последней, второй с предпоследней и т. д. ...
C++ Зачем здесь "y"? Разбираю код, решения задач, учусь... Но тут не могу понять. В общем суть задачи: Даны натуральное число m, целые числа а1, ...,аm и целочисленная квадратная матрица порядка m. Строку с номером i... http://www.cyberforum.ru/cpp-beginners/thread1010904.html
C++ задана последовательность, вычислить cумму ряда
дана последовательность 1/1-x=1+x+x^2+x^3+... вычислить cумму ряда помогите с реализацией Добавлено через 14 минут Использовать классы
C++ часы в консоли
Такой вопрос, допустим я пишу в консольке прогу, и хочу запилить часы в угол консоли, часы делаю через Sleep(1000), понимаю что это не есть правильно, но всё же иначе пока не умею, всякими там...
C++ Динамический массив http://www.cyberforum.ru/cpp-beginners/thread1010851.html
1. «Рабочий»: фамилия; имя; отчество; домашний адрес (почтовый индекс, страна, область, район, город, улица, дом, квартира); национальность; дата рождения (год, месяц число); № цеха; табельный...
C++ Динамические структуры 1. однонаправленный связанный список содержит целые числа. Найти наибольшее из них. Кроме того, обеспечить просмотр списка, удаление отрицательных и вставку нового элемента после заданного. 2.... подробнее

Показать сообщение отдельно
Entii
0 / 0 / 0
Регистрация: 17.11.2013
Сообщений: 3
19.11.2013, 22:49  [ТС]
UP
Решил таки, однако проблема оказалась не со скоростью( хотя и с ней тоже, но не такая ужасная), а с памятью. Используется BFS:


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
#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 
using namespace std; 
struct node  
    { 
        vector<string> v; //числа, которые должна просмотреть наша нода(node) 
        int p;//сколько денег будет потрачено при случае с текущей нодой 
        string t;//само значение ноды 
        node(vector<string> a,int b,string c){v=a;p=b;t=c;} 
    }; 
int a,m,n,p[100]; 
long long mn=999999999999; 
vector<string> k; 
vector<node> nodes; 
ifstream in("input.txt"); ofstream out("output.txt"); 
 
 
 
int main() 
{ 
    in>>a>>m>>n;//считываем данные из файла. а - количество названных чисел, м - длина числа, н - основание системы счисления  
    for (int i=0; i<m; i++) 
        in>>p[i];//считываем цену за угаданную цифру 
    for (int i=0; i<a; i++) 
        {string temp=""; in>>temp; k.push_back(temp);} // считываем сами числа 
    node nd(k,0,""); 
    nodes.push_back(nd);//создаем и пихаем в вектор первую пустую ноду 
    int *pr= new int[n];//массив возможных следующих цен 
    vector<string> *z=new vector<string>[n];//массив возможные следующих списков для перебора ноды 
    for (int i=0; i<nodes.size(); i++) 
    { 
 
        node temp=nodes[i];//текущая нода 
        int d =temp.t.size();//длина значения текущей ноды 
 
        for (int j=0; j<n; j++) 
            {z[j].clear(); pr[j]=temp.p;}//обнуляем наши массивы 
        if (d!=m)//если мы не дошли до максимальной длины числа 
        { 
        for (int j=0; j<temp.v.size(); j++) 
        { 
            z[int(temp.v[j][d]-'0')].push_back(temp.v[j]); 
            pr[int(temp.v[j][d]-'0')]+=p[d]-(d>0?p[d-1]:0);//кидаем наши варианты в массивы. 
        } 
        } 
        for (int j=0; j<n; j++) 
        { 
            if (z[j].size()==0 || d==m || temp.p>mn)//если мы дошли до максимума, или вариантов больше нету, или цена уже точно не подходит 
            { 
                if (mn>temp.p) mn=temp.p;//сохраняем новую лучшую цену 
            } 
            else 
            { 
                nodes.push_back(node(z[j],pr[j],(temp.t+char(j+'0'))));// иначе пихаем новую ноду в вектор 
            } 
        } 
        nodes.erase(nodes.begin());//удаляем текущую ноду 
        i--; 
    } 
    out<<mn; 
}
Решение через DFS сильно упиралось в скорость.
Как работает добавление вариантов в массив:
000 010 100 110
Запускаем программу, она создает первую пустую ноду.
Потом циклом смотрит на v[j][d] - то есть на d цифру у варианта j. А d у нас равно длине значения нашей ноды. Значит, если значение ноды пустое, d=0, значит смотрим на первую цифру. В следующих нодах d увеличивается, тем самым мы смотрим уже следующие цифры.

Как можно оптимизировать сие детище? Либо же здесь деревья совсем не подойдут?
P.S. переменные называются так убого из-за оценки кода по количеству символов.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru