迭代分治

Question

这段代码，在每一个循环循环中，都会创建两个更小的段，并将其添加到数字0中。问题是，如果你除以50，你得到25和25，如果你分裂51，你也得到25。这个x和y应该表示数组索引，因此它们从0开始。如果您知道更好的迭代算法(不能使用递归)，我会很高兴看到它，但是我真的很想用这种方式解决这个问题(除非它无法完成)。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int n;
    int a, b, x, r, y;
    printf("Enter N: ");
    scanf("%d", &n);
    a = 0;
    b = n - 1;
    x = a;
    y = b;
    r = b;
    printf(" %2d %2d\n", a, b);
    while(b > 1)
    {
        r /= 2;
        while(x < n - 1)
        {
            printf(" %2d ", x);
            y = x + r;          //if(something) y = x + r - 1;
            printf("%2d", y);   //else  y = x + r; 
            x = y + 1;
        }
        x = a;
        b = r;
        y = b;
        putchar('\n');
    }
    return 0;
}

产出：

Enter N: 50
  0 49
  0 24 25 49
  0 12 13 25 26 38 39 51
  0  6  7 13 14 20 21 27 28 34 35 41 42 48
  0  3  4  7  8 11 12 15 16 19 20 23 24 27 28 31 32 35 36 39 40 43 44 47 48 51
  0  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

Press [Enter] to close the terminal ...

Answer 1

这是一个广度优先遍历问题，应该用实现.我不认为有一种简单的方法来实现广度优先递归，所以迭代方法必须这样做。以下是一个粗略的算法：

1)创建两个队列，q和p，包含初始范围[a, b]。

​

2)当p不是空的时候，将元素从p中排掉并打印出来。

​

3)当q不是空的时候，从q中排出一个元素[i, j]，并将两个新的范围[i, (i + j) / 2]和[(i + j) / 2 + 1, j]排队到p中。

​

4)将p复制到q。

​

5)如果q的大小为a + b + 1，那么您就完成了。否则，回到第二步。

下面是我在C#中的实现：

using System;
using System.Collections.Generic;

struct Pair
{
    public int a;
    public int b;

    public Pair(int a, int b)
    {
        this.a = a;
        this.b = b;
    }
}

class Program
{
    static void Main()
    {
        Console.Write("Enter a number: ");
        int size = int.Parse(Console.ReadLine());

        Queue<Pair> queue = new Queue<Pair>();
        queue.Enqueue(new Pair(0, size));

        bool lastRound = false;

        do
        {
            if (queue.Count == size + 1)
            {
                lastRound = true;
            }

            Queue<Pair> temporary = new Queue<Pair>(queue);

            while (temporary.Count > 0)
            {
                Pair pair = temporary.Dequeue();

                if (pair.b - pair.a == 0)
                {
                    Console.Write("{0} ", pair.a);
                }
                else
                {
                    Console.Write("{0}-{1} ", pair.a, pair.b);
                }
            }

            Console.WriteLine();

            while (queue.Count > 0)
            {
                Pair pair = queue.Dequeue();

                if (pair.b - pair.a == 0)
                {
                    temporary.Enqueue(new Pair(pair.a, pair.b));
                }
                else
                {
                    temporary.Enqueue(new Pair(pair.a, (pair.a + pair.b) / 2));
                    temporary.Enqueue(new Pair((pair.a + pair.b) / 2 + 1, pair.b));
                }
            }

            queue = temporary;
        } while (!lastRound);
    }
}

这是它的产出：

Enter a number: 20
0-20
0-10 11-20
0-5 6-10 11-15 16-20
0-2 3-5 6-8 9-10 11-13 14-15 16-18 19-20
0-1 2 3-4 5 6-7 8 9 10 11-12 13 14 15 16-17 18 19 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Answer 2

做谷歌搜索快速排序。您将发现许多使用此技术的代码示例。

Answer 3

当你除数时，你需要决定是否有余数(取决于你分裂的数字是奇数还是偶数)。

您需要以不同的方式处理这两种不同的场景。你还必须决定把额外的数字放在哪里(上半场还是下半场)。

也许一种可能的修改是有两个r来跟踪这两个半程。