ሁለት የተሰጡ ድርድሮች ከተለዋጭ አካላት ውስጥ ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድር ይፍጠሩ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Directi Karat የ PayPal ቴሊዮ Yandex
ሰልፍ ዳግም መጥፋት

ችግሩ “በሁለት የተሰጡ ድርድሮች ከተለዋጭ አካላት ተለዋጭ አካላት ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድሮችን ይፍጠሩ” የሚለው ሁለት የተደረደሩ ድርድር አለዎት ማለት ነው ፡፡ የችግሩ መግለጫ ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድሮችን ለማግኘት ይጠይቃል ፣ ይህ ቁጥር ከተሰጡት ሁለት ድርድሮች በአማራጭ መዘጋጀት አለበት ፡፡

ለምሳሌ

ArrA[] = {9, 12, 66}
ArrB[] = {10, 15, 25}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

ማስረጃ

ሁሉም ተለዋጭ ቁጥሮች ከተለያዩ ድርድሮች እና የተደረደሩ ናቸው።

ሁለት የተሰጡ ድርድሮች ከተለዋጭ አካላት ውስጥ ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድር ይፍጠሩ

 

አልጎሪዝም

  1. የመጠን ድርድር መጠን ያውጁ መ + n (የሁለቱም ድርድር አጠቃላይ ርዝመት)።
  2. መኖሩን ያረጋግጡ boolCondition እውነት ነው,
    1. ከዚያ የውጤቱ ድርድር ርዝመት ከ 0 ጋር እኩል አለመሆኑን ያረጋግጡ ፣ ከዚያ የውጤት ድርድርን ያትሙ።
      1. ድርድርን ያቋርጡ አርአር እና የሚከተሉትን ያረጋግጡ
        1. የውጤቱ ድርድር ርዝመት 0 ከሆነ የአሁኑን ንጥረ ነገር ወደ ውፅዓት ድርድር ይቅዱ ከዚያ ተግባሩን እንደገና ይደውሉ።
    2. አለበለዚያ የአሁኑ የድርድር አካል ከቀዳሚው የውጤት ድርድር ንጥረ ነገር የበለጠ ከሆነ ፣ ከዚያ ኤለሜንቱን ይቅዱ አርአር ወደ ውፅዓት ድርድር እና እንደገና ተግባሩን ይደውሉ።
  3. ሌላ ጊዜ “boolCondition” ሐሰት ከሆነ ፣ ከዚያ ተሻገሩ ArrB እና የአሁኑ ንጥረ ነገር ያረጋግጡ ArrB ከውጤቱ ድርድር አሁን ካለው ንጥረ ነገር ይበልጣል
      1. እውነት ከሆነ ከዚያ ኤለሜንቱን ከ ArrB ወደ ውፅዓት ድርድር እና እንደገና ተግባሩን ይደውሉ።

ማስረጃ

ችግሩ “በሁለት የተሰጡ ድርድሮች ከተለዋጭ አካላት ተለዋጭ አካላት ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድሮችን ይፍጠሩ” በሚከተለው መንገድ ሊፈታ ይችላል። እዚህ ሁለት የተደረደሩ ድርድሮች ተሰጠን አርአርArrB. የተሰጡት ሁለቱም ድርድሮች በቅደም ተከተል የተቀመጡ ናቸው ፡፡ ስለዚህ የሚቻለውን ሁሉ መፈለግ አለብን ድርድሮች በተስተካከለ ሁኔታ ሊገነባ ይችላል። በውጤቱ ውስጥ እያንዳንዱ ተለዋጭ አካል ከተለያዩ ድርድርዎች መምጣት ያለበት ሌላ ሁኔታም አለ ፡፡

ሁሉንም ሊሆኑ የሚችሉ የውጤት አቅርቦቶችን ለማግኘት ያንን ተግባር እንደገና እንጠራዋለን ፡፡ ከዚያ የሚመረጡ አካላትን የሚከታተል የቦሊያን ተለዋዋጭ እንጠብቃለን። ያ ንጥረ ነገሩ ከአሁኑ የ ArrA ወይም ከ ArrB ነው። የቦሊው ተለዋዋጭ እውነተኛ ከሆነ ከዚያ ከመጀመሪያው ድርድር አርአር አንድ አባል እንመርጣለን። ሌላኛው የቦሊው ተለዋዋጭ ሐሰተኛ ከሆነ ፣ እኛ ከሁለተኛው ድርድር አርርቤ ውስጥ ያለውን ንጥረ ነገር እንመርጣለን። የቦሊያን ተለዋዋጭ ከሆነ የእውቀቱ ርዝመት ከ 0 ጋር እኩል አለመሆኑን ወይም በቀላሉ ከ 0 ያልበለጠ መሆኑን እንፈትሻለን ፣ ከዚያ የውጤት ድርድርን ለማተም በምንሄድበት እያንዳንዱ ጊዜ።

የቦሊው ሁኔታ እውነት ከሆነ የድርጅቱን አርአራን እናቋርጣለን ፡፡ ከዚያ የአሁኑን የድርድር አካል ወደ ውፅዓት ድርድር ይቅዱ። ከዚያ ሁሉንም አስፈላጊ ክርክሮች ወደ እሱ በማስተላለፍ ተግባሩን እንደገና እንጠራዋለን ፡፡ የቦሊው ሁኔታ ሐሰት ከሆነ። ከዚያ የእኛን የውጤት ድርድር ለመቅዳት እና ለማዘመን ArrB ን እንጠቀማለን። እና የውጤቱ ድርድር ርዝመት 0 በሚሆንበት ጊዜ ሁሉ ፣ ከዚያ ድርድርን ያትሙ።

ኮድ

ሁሉንም ሊደረደሩ ድርድሮች ለማመንጨት የ C ++ ኮድ

#include<iostream>
using namespace std;

void printArray(int arr[], int n);

void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, bool flag)
{
    if (flag)
    {
        if (len)
            printArray(output, len+1);

        for (int k = i; k < m; k++)
        {
            if (!len)
            {
                output[len] = ArrA [k];
                getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
            }
            else
            {
                if (ArrA [k] > output[len])
                {
                    output[len+1] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                }
            }
        }
    }
    else
    {
        for (int l = j; l < n; l++)
        {
            if (ArrB[l] > output[len])
            {
                output[len+1] = ArrB[l];
                getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
            }
        }
    }
}

void generate(int ArrA [], int ArrB[], int m, int n)
{
    int output[m+n];
    getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int ArrA [] = {9, 12, 66};
    int ArrB[] = {10, 15, 25};
    int n = sizeof(ArrA)/sizeof(ArrA [0]);
    int m = sizeof(ArrB)/sizeof(ArrB[0]);
    generate(ArrA, ArrB, n, m);
    return 0;
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

ሁሉንም ሊሆኑ የሚችሉ የተደረደሩ ድርድሮችን ለማመንጨት የጃቫ ኮድ

class GeneratedSortedArray
{
    public static void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, boolean flag)
    {
        if (flag)
        {
            if (len!=0)
                printArray(output, len+1);

            for (int k = i; k < m; k++)
            {
                if (len==0)
                {
                    output[len] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
                }
                else
                {
                    if (ArrA [k] > output[len])
                    {
                        output[len+1] = ArrA [k];
                        getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                    }
                }
            }
        }
        else
        {
            for (int l = j; l < n; l++)
            {
                if (ArrB[l] > output[len])
                {
                    output[len+1] = ArrB[l];
                    getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
                }
            }
        }
    }

    public static void generate(int ArrA [], int ArrB[], int m, int n)
    {
        int output[]=new int[m+n];
        getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
    }
    
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String [] args)
    {
        int ArrA [] = {9, 12, 66};
        int ArrB[] = {10, 15, 25};
        int n = ArrA.length;
        int m = ArrB.length;
        generate(ArrA, ArrB, n, m);
    }
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n1 ^ 2 + n2 ^ 2) የት “N1” “N2” የ ArrA እና ArrB ርዝመት ናቸው። ንጥረ ነገሮቹ ሲለዋወጡ ያ ArrA ነው [0] <ArrB [0] <ArrA [1] <ArrB [1] this በዚህ አጋጣሚ በድምሩ n1 ^ 2 + n2 ^ 2 ሊሆኑ የሚችሉ ንዑስ ጥቅሞችን ማግኘት እንችላለን ፡፡ ስለዚህ አንድ ባለ ብዙ ቁጥር ጊዜ ውስብስብነት።

የቦታ ውስብስብነት

ኦ (n1 + n2) የት “N1” “N2” የ ArrA እና ArrB ርዝመት ናቸው። ክፍተት በውጤቱ ድርድር ይወሰዳል እና መጠኑ n1 + n2 ስለሆነ። የቦታ ውስብስብነት መስመራዊ ነው።