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

Найти ошибку в реализации алгоритма n - путевого слияния - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Счетчик циклов http://www.cyberforum.ru/cpp-beginners/thread908537.html
помогите найти ошибку: #include <stdio.h> #include <iostream> #include <cstdlib> using namespace std; int main(int argc, char** argv) { int loopCount; puts("enter loopCount"); scanf("%d",&loopCount); while(loopCount>0)
C++ Циклический сдвиг матрицы Есть динамическая матрица, и есть обычный сдвиг на N элементов на право. как сделать сдвиг по рисунку? #include <stdlib.h> #include <iostream> #include <stdio.h> using namespace std; void shiftRight( int **matrix, int rows, int columns, int shift); int main() http://www.cyberforum.ru/cpp-beginners/thread908484.html
Сделать строки класса стринг в консоли (слова, в которых сразу после каждой гласной буквы стоит хотя бы одна согласная) C++
Разработайте программу, запрашивающую строки, слова которых разделены пробелами и знаками препинания и выводящую в столбик, слова этой строки, обладающие указанными свойствами, или сообщение «таких слов нет». Слова, в которых сразу после каждой гласной буквы стоит хотя бы одна согласная. помогите пожалуйста,не могу решить
C++ Вывести матрицу в файл
Собственно, доброго утра! Вопрос в следующем, на функции я вынос в файл сделал, но как вывести исходную матрицу в файл? Заранее спасибо! #include <stdio.h> #include <conio.h> #include <iostream.h> #include <iomanip.h> #include <math.h> FILE *f; const int MAX = 10; void Print(int a, int n) {
C++ Найти разницу между средним арифметическим положительных и отрицательных элементов столбцов с нечётными номерами матрицы http://www.cyberforum.ru/cpp-beginners/thread908473.html
Доброго времени суток! Ребята, подскажите пожалуйста, что это за бредятина и чего хочет от меня преподаватель?) Дали на контрольную работу задание. Уже трижды голову сломал. Сдать нужно завтра, как всегда придержал на последний срок.(( Найти разницу между средним арифметическим положительных и отрицательных элементов столбцов с нечётными номерами матрицы А(7,10). У меня из выше...
C++ input»word: необъявленный идентификатор #include "stdafx.h" #include <iostream> #include <fstream> #include <cstring> using namespace std; int main() { char word; подробнее

Показать сообщение отдельно
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
21.06.2013, 10:16     Найти ошибку в реализации алгоритма n - путевого слияния
Доброе утро.
Нужно реализовать алгоритм n - путевого слияния (n - аргумент функции). Некоторые операции проходят неверно, причём вычислить ошибку никак не удаётся (подробности ниже). Вот код:
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
namespace MultiMerge {
 
const int empty=0x80000000;
 
struct Buffer {
    //буфер для работы с ключами
    Buffer():prev(empty),curr(empty) { };
 
    int prev;
    int curr;
};
 
void create_files(vector<string>& fnames, int n)
{
    //создание списка имён вспомогательных файлов
    string templ="_File_for_MultiMerge";
    for (int i=0; i<2*n; ++i)
        fnames.push_back(templ+to_string(i));
 
    //создание самих файлов
    ofstream ofs;
    for (int i=0; i<2*n; ++i) {
        ofs.open(fnames[i]);
        ofs.close();
    }
}   
 
int split(const string& source, vector<string>& workfiles, int n)
{
    //распределение элементов из исходного файла, 
    //возвращается кол-во возрастающих серий в source
 
    ifstream ifs(source);   
    if (!ifs) throw runtime_error("split: can't open source file");
 
    vector<ofstream> vofs(n);       
    for (int i=0; i<n; ++i) {
        vofs[i].open(workfiles[i]);
        if (!vofs[i]) throw runtime_error("split: can't open one of auxiliary file");
    }
 
    int series(0);                          
    int write_num(0);                       //номер вспомогательного файла, в который идёт запись
    int buffer1(empty), buffer2(empty);     //буферы для чтения ключей и определения границ серий
    while (true) {
        if (buffer2==empty && !(ifs>>buffer2)) {
            ++series;
            break;
        }
        if (buffer2>=buffer1) {
            vofs[write_num]<<buffer2<<" ";
            buffer1=buffer2;
            buffer2=empty;
        }
        else {                              //конец очередной серии
            ++series;
            write_num=(write_num+1)%n;
            buffer1=empty;                  //начало новой серии, условие (buffer2>=buffer1)==true
        }
    }
 
    return series;
}
 
void sort(const string& source, int n)
{
    //source - исходный файл, n - путевое слияние
    if (n<2) throw runtime_error("sort: not enough auxiliary files for sorting");
 
    vector<string> fnames;
    create_files(fnames,n);
    int series=split(source,fnames,n);  //кол-во серий на каждом очередном этапе
 
    vector<int> table_dir(2*n);         //таблица, первые n значений - индексы сливаемых файлов
    for (int i=0; i<2*n; ++i)
        table_dir[i]=i;
 
    vector<int> table_from(n);          //таблица для отслеживания окончания серий и окончания данных в сливаемых файлах
    vector<Buffer> v_buf(2*n);          //вектор буферов для каждого файла, из которого на данном этапе сливаются ключи
    while (series>1) {
 
        int cnt1(n), cnt2(n);           //число непустых файлов; число файлов, в которых текущая серия ещё не закончилась
        if (series<n) 
            cnt1=cnt2=series;
 
        int file_for_write=n;               //table_dir[file_for_write] - индекс файла, в который идёт запись
        series=0;
 
        for (int i=0; i<n; ++i) {
            table_from[i]=table_dir[i];         //подготовка таблицы
            v_buf[table_from[i]].prev=empty;    //подготовка буферов (1)
        }
        
        vector<fstream> v_fs(2*n);              //подготовка файлов
        for (int i=0; i<2*n; ++i) {
            v_fs[i].open(fnames[table_dir[i]]); 
            if (!v_fs[i]) throw runtime_error("sort: can't open one of auxiliary files during merge stage");
        }
        
        for (int i=0; i<cnt1; ++i)
            v_fs[table_from[i]]>>v_buf[table_from[i]].curr; //подготовка буферов (2)
 
        cout<<"Buffers before merge: ";
        for (int i=0; i<table_from.size(); ++i)
            cout<<v_buf[table_from[i]].curr<<", ";
        cout<<endl;
        while (cnt1) {
    
            //поиск минимума
            int nmin(0);
            for (int i=0; i<cnt2; ++i) {
                if (v_buf[table_from[i]].curr<v_buf[table_from[nmin]].curr) nmin=i;
            }
            cout<<"min="<<v_buf[table_from[nmin]].curr<<endl;
 
            //запись минимума
            v_fs[table_dir[file_for_write]]<<v_buf[table_from[nmin]].curr<<" ";
            v_buf[table_from[nmin]].prev=v_buf[table_from[nmin]].curr;
 
            //работа с буфером, проверки на конец серии и конец файла
            if (!(v_fs[table_from[nmin]]>>v_buf[table_from[nmin]].curr)) {
                --cnt1;
                --cnt2;
                swap(table_from[nmin],table_from[cnt1]);
                swap(table_from[nmin],table_from[cnt2]);
            } else if (v_buf[table_from[nmin]].curr < v_buf[table_from[nmin]].prev) {
                --cnt2;
                swap(table_from[nmin],table_from[cnt2]);
            }
            cout<<"cnt1 == "<<cnt1<<", cnt2 == "<<cnt2<<endl;
            cout<<"Buffers: ";
            for (int i=0; i<table_from.size(); ++i)
                cout<<v_buf[table_from[i]].curr<<", ";
            cout<<endl<<endl;
 
            //проверка на конец серий в каждом файле
            if (cnt2==0) {
                ++series; //неправльная работа с сериями (условие!)
                cnt2=cnt1;
                if (file_for_write<2*n-1)   //меняем файл для записи
                    ++file_for_write;
                else
                    file_for_write=n;
            }
 
        }
        cout<<"series=="<<series<<endl;
        cout<<"-------------------------------------------------"<<endl;
        
        //подготовка к следующему слиянию: блоки из n файлов меняются ролями
        for (int i=0; i<n; ++i)
            swap(table_dir[i],table_dir[i+n]);
        system("pause");
    }
 
    //результат должен  в v_fs[table_dir[0]]
    //перенос результата в исходный файл
    /*ifstream ifs(fnames[table_dir[0]]);
    ofstream ofs(source);
    if (!ifs || !ofs) throw runtime_error("sort: can't return result in source file");
    int buffer;
    while (ifs>>buffer)
        ofs<<buffer<<" ";*/
 
    /*удаление вспомогательных файлов*/
    /*for (int i=0; i<fnames.size(); ++i)
        remove(fnames[i].c_str());*/
}
 
}
Функции split и create_files отлажены. Тестировал на последовательности 10, 9, 8, 7, 6, 5, 4, 3, 2 (сортировать нужно по возрастанию), первый этап проходит верно: series == 3, получаем последовательности 8,9,10 | 5,6,7 | 2, 3, 4. Однако на следующем шаге перед началом слияния в буферы снова попадают 10,9,8 вместо 8,5,2 => зацикливание.
Подскажите:
1) В чём же проблема?
2) Можно ли как-то упростить код, нет ли в моё варианте слишком большого кол-ва ненужных операций?
Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru