د A2-b1-a1-b2-a2-b3 په توګه د 3n انټیرز شفل کړئ - پرته د اضافي ځای کارولو پرته bn


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب DE شا ايکسپيډيا انځورونه په حقیقت کی پیرو یو
پیشه تقسیم او فتح تکرار

ستونزه بیان

تاسو ته ورکول کیږي سور of ضمیمه. مسئله "د 2 انټرلونو شکل د a1-b1-a2-b2-a3-b3 - .. bn پرته د اضافي ځای کارولو څخه پوښتنه کوي" په صف کې د ټولو شمیرو شفل کول وغواړي داسې شمیرې چې ورته دي (x0 ، x1 ، x2 ، x3 ، y0 ، y1 ، y2 ، y3) به د x0 ، y0 ، x1 ، y1 ، x2 ، y2 ، x3 ، y3 او داسې نورو په شان بدلون ومومي.

بېلګه

arr[]={1, 3, 5, 7, 2, 4, 6, 8}
1, 2, 3, 4, 5, 6, 7, 8

تشریح

که موږ د لومړي درې شمیرو سره پرتله کړو نو د x0 ، x1 ، x2 په څیر وي او راتلونکی درې شمیرې به د y0 ، y1 ، y2 په څیر وي ، او دا به په x0 ، y0 ، x1 ، y1 ، x2 ، y2 کې تنظیم شي.

د A2-b1-a1-b2-a2-b3 په توګه د 3n انټیرز شفل کړئ - پرته د اضافي ځای کارولو پرته bn

الګوریتم ته شفل 2n انټیجر د a1-b1-a2-b2-a3-b3 په توګه - .. bn د اضافي ځای کارولو پرته

1. Find out the middle index of the array.
2. While middleIndex greater than 0, set count and swappingIndex to middleIndex.
  1. While the count is greater than 0, do the following steps.
    1. Swap the values at swappingIndex and swappingIndex +1(value next to swappingIndex).
    2. Increase the value of swapping index by 1.
  2. Decrease the value of middleIndex by 1.
3. Print the array.

تشریح

موږ ورکړل سور of عدد.  بیا موږ څخه غوښتنه کیږي چې ټول عدد ارزښتونه په ځانګړي توګه ورکړل شوي ب mannerه بدل کړئ. موږ به د صف نیمایی برخه تیر کړو. او ټول هغه ارزښتونه بدلول چې د الګوریتم مطابق مخې ته راځي. لومړی ، موږ ګورو چې صفونه باید خالي نه وي. ځواب هم ، د صفونو اوږدوالی باید حتی وي. له همدې امله موږ دا حالت ګورو چې د تیرې اوږدوالي باید عجیب نه وي. که د پورته ذکر شوي شرایطو څخه کوم یو غلط وي ، نو دا به محصول نه تولیدوي.

موږ به د صف مینځنی شاخص ومومو او بیا به د هغه شاخص ارزښت او د هغې د راتلونکي شاخص ارزښت وګورو او په ساده ډول هغه بدل کړئ. د دې لپاره ، موږ ځړول شوي استعمال کوو پداسې حال کې چې په لومړي ځل لوپ کې. بیا موږ دا د اوسني شاخص څخه 0 ته تیروو او د مینځنۍ شاخص ارزښت کمولو ته دوام ورکوو. دننه دننه پداسې حال کې چې، موږ به د اوسني شاخص په څیر ورته ارزښت swappingIndex ته زیرمه کړو او بیا د swappingIndex ارزښت او خپل راتلونکی ارزښت واخلو او هغه بدل کړو. د دوهم سویپ لپاره ، د سویپینګ انډیکس ارزښت لوړ کړئ او د اوسني سویپینګ انډیکس او د هغې د راتلونکي شاخص ارزښت لپاره بدلول غواړئ.

د راتلونکي تعقیب لپاره ، موږ به د مینځنۍ شاخص ارزښت کم کړو. ترڅو دا وکولی شي د صفونو له مخې څخه ارزښتونه واخلي. په ورته ډول ، د شمیرو او تبادلې انډیکس به د مینځنۍ شاخص ارزښت سره ورته وي چې موږ د صفونو پخوانیو ارزښتونو تیروو. د ټولو بدلولو وروسته چې موږ ترسره کړي ، موږ به دا صف چاپ کړو ، او ټولې شمیرې به په یو ټاکل شوي شکل سره بدلې شي.

کوډ

د A2-b1-a1-b2-a2-b3 په توګه د 3n انټیجرونو شفر کول C ++ کوډ - .. د اضافي ځای کارولو پرته bn

#include<iostream>
using namespace std;

void shuffleInt(int arr[], int n)
{
    if (arr == NULL || n % 2 == 1)
        return;

    int middleIndex = (n - 1) / 2;

    while (middleIndex > 0)
    {
        int countIndex = middleIndex, swappingIndex = middleIndex;

        while (countIndex -- > 0)
        {
            int temp = arr[swappingIndex + 1];
            arr[swappingIndex + 1] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            swappingIndex++;
        }
        middleIndex--;
    }
}
int main()
{
    int arr[] = {1, 9, 25, 4, 16, 36};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffleInt(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i]<<" ";
}
1 4 9 16 25 36

د جاوا کوډ د 2n انټیجرونو ته د a1-b1-a2-b2-a3-b3 په توګه - .. bn د اضافي ځای کارولو پرته

class Shuffle2nIntegers
{
    public static void shuffleInt(int[] arr)
    {

        if (arr == null || arr.length % 2 == 1)
            return;

        int middleIndex = (arr.length - 1) / 2;


        while (middleIndex > 0)
        {
            int countIndex = middleIndex, swappingIndex = middleIndex;

            while (countIndex -- > 0)
            {
                int temp = arr[swappingIndex + 1];
                arr[swappingIndex + 1] = arr[swappingIndex];
                arr[swappingIndex] = temp;
                swappingIndex++;
            }
            middleIndex--;
        }
    }

    public static void main(String[] args)
    {
        int arr[] = {1, 9, 25, 4, 16, 36};
        shuffleInt(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print( arr[i]+" ");
        System.out.println();
    }
}
1 4 9 16 25 36

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n ^ 2) هلته "n" په صف کې د عناصرو شمیر دی. لکه څنګه چې هر ځل موږ یو له بل سره د مینځنۍ انډیکس کمو. مګر داخلي لوپ د منځنۍ انډیکس شمیر وختونو لپاره ځي. تاسو کولی شئ دا د ساده دوه ځليدونکي لوپونو په توګه په پام کې ونیسئ چیرې چې بیروني لوپ له i = 0 څخه n داخلي لوپ له i + 1 څخه چلیږي. پدې توګه د وخت پیچلتیا ډیره ده.

د ځای پیچلتیا

O (1) ، ځکه چې الګوریتم یو ځای کې الګوریتم دی. دا ټول هغه عملیات دي چې ترسره کیږي د ابتدايي عناصرو ځای نیسي. او هیڅ یو نوی تیر شوی ندي.