Алгоритъм за сливане на две наредени редици

Описаният алгоритъм за сливане на две наредени редици е валиден за две предварително сортирани както във възходящ ред, така и в низходящ ред. Предварително се знаят броят на елементите във всяка от редиците P1, P2, както и вида на наредбата им. Броят на елементите в новата (третата) редица ще бъде P = P1 + P2. Използват се допълнително две променливи M1, M2 съдържащи поредния номер елемент за всяка от редиците. Стъпките на алгоритъма са следните:

  1) Сравняват се поредните елементи от двете редици с номер M1 и M2.
  2) Ако елементът с номер М1 е по-малък или равен от елементът с номер М2 в третата редица се записва елементът с номер М1. Променливата М1 увеличава стойността си с 1.
   Ако елементът с номер М1 е по-голям от елементът с номер М2 в третата редица се записва елементът с номер М2. Променливата М2 увеличава стойността си с 1.
  3) Проверява се дали М1<Р1. Ако е да отива на стъпка 5), ако е не на стъпка 1).
  4) Проверява се дали М2<Р2. Ако е да отива на стъпка 6), ако е не на стъпка 1).
  5) Прехвърлят се останалите елементи от редица 2 в редица 3. Отива на стъпка 7.
  6) Прехвърлят се останалите елементи от редица 1 в редица 3. Отива на стъпка 7.
  7) Край на алгоритъма.

    Следващата примерна програма дава решена задача за сливане на две наредени редици. Редиците са представени като стойности в два едномерни масива.
 
  Да се състави програма, която като входни данни има 2 едномерни сортирани масива, съдържащи естествени числа от интервала [-5000 + 5000]. В общия случай двата масива са с различен брой елементи.
  Да се изведе на екрана резултата от обединението на 2-та масива като елементите на новообразувания масив са също сортирани.
  Пример:
  {1,3,5,7,9,11,113} и {2,4,6,8,10,12,14,16,18,20}
  Изход:
  1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,113
 
#include <iostream>

#include<math.h>

using namespace std;

 

int main()

{

const int n1=7, n2=10;//konstanta za broq elementi w redica 

int mas1[n1]={1,3,5,7,9,11,113};  // naredeni elementi w 1-wa redica  


int mas2[n2]={2,4,6,8,10,12,14,16,18,20};// naredeni elementi wyw 2-ra redica 

int mas3[n1+n2];

int i,n,b1,b2;


  cout<<"Da se systawi programa, koqto kato whodni danni ima 2\n";

  cout<<"sortirani ednomerni masiwa sydyrvashi celi chisla w\n";

  cout<<"interwala [-5000 + 5000]. W obshiq sluchaj masiwite sa s\n";


  cout<<"razlichen broj promenliwi. Da se izwede na ekrana rezultatyt\n";

  cout<<"ot obedinqwane na dwata masiwa kato elementite sa sortirani\n";

  cout<<"w ednomeren masiw - sliwane na dwe naredeni redici.\n";

  cout<<"Primer: {1,3,5,7,9,11,113} i {2,4,6,8,10,12,14,16,18,20}\n";

 cout<<"Izhod 1,2,3,4,5,6,7,8,9,10,11,12,14,16,18,20,113\n";



  cout<<"Nachalno systoqnie na dwata masiwa - redici: \n";

 for (i=0;i<n1;i++) {cout<<" "<<mas1[i];}

  cout<< endl;

  for (i=0;i<n2;i++) {cout<<" "<<mas2[i];}


  cout<< endl;


  n=n1+n2;//dylvinata na nowiq masiw - redica e sumarnata dylvina ot 2-ta masiwa

  b1=b2=0;//poziciqta w dwata masiwa 

  for (i=0;i<n;i++)

  { if (b1<n1 && b2<n2) //wse oshe ima newywedeni elementi i ot dwata masiwa


    {if (mas1[b1]<mas2[b2])

      {//koj ot dwata masiwa sydyrva po-malko chislo s tozi indeks

       mas3[i]=mas1[b1];    b1++;}//broq weche wywedeni elementi 

       else

       { mas3[i]=mas2[b2];   b2++;}//kraj na prowerkata 

     }//if (b1<n1 && b2<n2


   else //edin ot dwata masiwa e weche izcqlo wyweden

    { if (b1<n1) {mas3[i] = mas1[b1]; b1++;}

     else   {mas3[i] = mas2[b2]; b2++;}

    }//kraj na prowerka dali ediniq ot masiwite e izcqlo wyweden

   } // kraj na pyrwiq cikyl

     

  cout<<"Obedineniqt masiw sydyrva: "<<endl;


  for (i=0;i<n;i++)  {cout<<" "<<mas3[i]; }

  cout<<endl;//pechat na obedineniq masiw

 system("pause");//zadyrva izpylnenieto na programata do natiskane na klawish ot klawiaturata

 return 0; //oswobovdawa zaetite sistemni resursi

} //kraj na programa - sliwane na dwe naredeni redici 
  

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Начало на страницата

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: