Слияние массивов

[pisarev-70]

Помогите мне решить задачку. Я уже все перепробовал. Ну ни как не получается.
Заданы три упорядоченных по возрастанию массива f[n], g[m], h[k].
Составить программу слияния этих массивов.
Благодарю всех, кто откликнулся.

[pproger]

влом мне расписывать, алгоритм простейший. нахаляву могу предложить такой способ

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v, m;

	int f[] = { 1, 3, 4, 6 };
	int g[] = { 1, 4, 5, 7, 8 };
	int h[] = { 6, 8, 9, 10 };

	merge(f, f + sizeof(f) / sizeof(f[0]), g, g + sizeof(g) / sizeof(g[0]), back_inserter(v));
	merge(v.begin(), v.end(), h, h + sizeof(h) / sizeof(h[0]), back_inserter(m));
	copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));

	return 0;
}

[RUSt88]

та тут простейшее решение на поверхности

три упорядоченных по возрастанию массива f[n], g[m], h[k].

указаны их размеры, значит они константны
следовательно завести новый массив
res[n + m + k] и и скопировать туда элементы предыдущих массивов

[Mandrivnyk]

и скопировать туда элементы предыдущих массивов

видимо, надо бы сначала узнать, как именно они должны сливаться...

[pproger]

2RUSt88

и скопировать туда элементы предыдущих массивов

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

2Mandrivnyk

видимо, надо бы сначала узнать, как именно они должны сливаться...

он же написал, слиянием

[Mandrivnyk]

2pproger

он же написал, слиянием

блин, опять конфликт терминологии -)
Мне почему-то сразу представилось, что, например, исходящий массив тоже должен быть отсортирован по возрастанию, причем именно в процессе слияния, а не потом.
или, еще интереснее, три массива должны быть "втасованы" друг в друга -- сначала в результирующий массив записываются первые элементы, причем тоже отсортированные по возрастанию относительно друг друга, потом вторые и так далее.
Иначе зачем бы была в постановке задачи информации о том, что исходные массивы отсортированы?

[pproger]

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

естественно после слияния результирующий массив должен получиться отсортированным, в этом и смысл слияния отсортированных последовательностей

[Mandrivnyk]

естественно после слияния результирующий массив должен получиться отсортированным, в этом и смысл слияния отсортированных последовательностей

согласен
+

[Ezhuk]

Есть идея как сделать. Минут через 20 скину наверно.

#include "stdio.h"

int main(){
const int m=4,n=6,k=5;
int f[m] = { 1, 4, 7,10 };
int g[n] = { 2, 5, 8, 11, 13,14 };
int h[k] = { 3, 6, 9, 12, 15 };
int fgh[m+n+k];
int x=0,y=0,z=0,i=0;
while(i<m+n+k){
if(x<m && y<n && z<k){
if(f[x]<=g[y] && f[x]<=h[z])
fgh[i]=f[x++];
else if(g[y]<=f[x] && g[y]<=h[z])
fgh[i]=g[y++];
else if(z<k)
fgh[i]=h[z++];}
else if(x<m && y<n && z>=k){
if(f[x]<=g[y])
fgh[i]=f[x++];
else
fgh[i]=g[y++];}
else if(x<m && y>=n && z<k){
if(f[x]<=h[z])
fgh[i]=f[x++];
else
fgh[i]=h[z++];}

else if(x>=m && y<n && z<k){
if(g[y]<=h[z])
fgh[i]=g[y++];
else
fgh[i]=h[z++];}
else if(x<m && y+z-n-k<=0)
fgh[i]=f[x++];
else if(y<n && x+z-m-k<=0)
fgh[i]=g[y++];
else
fgh[i]=h[z++];
printf("%d ", fgh[i++]);
}
}