0

这段代码在每个循环周期中创建了两次较小的段，并将其添加到数字 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 ...
4

4 回答 4

2

谷歌搜索快速排序。您会发现许多使用这种技术的代码示例。

于 2013-08-02T15:22:13.817 回答
2

这是一个广度优先遍历问题，应该使用队列来实现。我认为没有一种简单的方法可以实现广度优先递归，因此必须采用迭代方法。下面是一个粗略的算法：

1）创建两个队列，q并且p，包含您的初始范围[a, b]。

                   在此处输入图像描述

2）当p不为空时，将一个元素从队列中取出p并打印它。

                   在此处输入图像描述

3) 虽然q不为空，但将一个元素[i, j]从队列中取出，q并将两个新范围[i, (i + j) / 2]和[(i + j) / 2 + 1, j]入队p。

                   在此处输入图像描述

4) 复制p到q.

                   在此处输入图像描述

5) 如果q大小为a + b + 1，那么你就完成了。否则，返回步骤 2。

这是我在 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
于 2013-08-02T18:49:47.613 回答
0

拆分数字时，您需要确定是否有余数（取决于您拆分的数字是奇数还是偶数）。

您将需要以不同的方式处理这两种不同的情况。您还必须决定将额外号码放在哪里（上半场或下半场）。

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

于 2013-08-02T15:28:09.083 回答
0

问题的根源是无法为每次迭代计算固定的跳跃大小（r）。每次迭代的常数 r 仅在起始数字是 2 的幂时才有效（尝试从 64 开始，您会发现一切都如您所愿）。对于任何其他数字，跳转大小 (r) 可以是 r 或 r+1，具体取决于先前的迭代是否将当前范围划分为偶数或奇数个元素。因此，在整个迭代过程中，r 的值可能不是一个常数。

一旦您看到当前迭代依赖于先前迭代的结果，就会弹出“堆栈”或“递归”这些词作为直接解决方案。这是因为需要先验状态信息来解决问题。

您的问题可能有一个纯粹的迭代解决方案，但我认为它需要一些有趣的数学或额外的内存来维护状态信息。

于 2013-08-02T18:44:26.967 回答