c++ - 递归地将一个数除以 2

Question

我一直对一个递归问题感到困惑。

我想将给定的数字(例如20)分为两部分，分别包含1到一半和一半到结束，现在这两个子数组应该以相同的方式划分，即1到一半和一半到结束，直到我们遍历所有元素。

请建议我如何通过递归或迭代来实现这一目标。

<小时/> ^{正在将评论转移到问题。}

假设输入是 1 和 20。输出将类似于:

1. 20/2 = 10 现在我们有两组数字(1 和 10)和(11 和 20)
2. 10/2 = 5，(20+10)/2=15 的后半部分。

这次迭代将以同样的方式运行，直到我们遍历完 1 到 20 之间的所有数字。

Answer 1

what i needed is...(1) in the first iteration i want 10. (2) in the second iteration i want 5, 15. (3) in the third iteration i want 3,8,13,18. and so on. – user4365176

我发现了一个工具(在我的库中)，我用它来将 vector (非递减整数)的内容传输到二叉树，这样简单的二叉树将(大部分)平衡。

这是我为了您的目的而简化的代码版本。此代码片段是类中的方法，因此以“m_”为前缀的 undefined variable (m_tree、m_ss、m_R)是该类的数据属性。 m_tree 是我自己开发的简单二叉树的实例，使用方法“insertVal(size_t i)”，m_ss 是指向 std::stringstream 的指针，m_R 是用户输入数字，范围。

“genSeqRR()”是递归的。它将一个范围切成两半，然后先处理右边，然后处理左边(有点按顺序深度优先的形式。目前，该顺序可能略有偏差。不知道如何描述。请参阅注释 2(在代码中) .

我还将这些序列插入到 AVL 树中(来自rosettacode.org/wiki)，但结果令人失望。可能没有错，但在这里没用。

您可以尝试使用红黑树来执行此插入序列。

<小时/>

代码后的示例输出:

// Generate a Sequence of size_t values over a fixed limited Range,
// Recursively using binary-pattern through the range, to achieve approximate
// balance when inserting into a simple binary tree.
//
// Note1: 'index' is range (0..N-1), value to insert is (indx+1) i.e 1..N
// Note2: prefer to insert bigger indx first
//
void genSeqRR(size_t depth, const size_t si,  const size_t bi)
  {
     size_t rng = bi - si; // big indx - small indx
     switch (rng)
     {

     default: // 3 or more elements, insert mi, and recurse
     {
        size_t delta = rng / 2;
        size_t    mi = si + delta; // mid index

        (void)m_tree->insertVal(mi+1);  // Note1

        // if(m_ss)
        *m_ss << "    rng:" << std::setw(3) << rng
              << "   dpth:" << std::setw(3) << depth  // depth of genSeqRR
              << "   iVal:" << std::setw(3) << mi+1
              << std::endl;

        // Note2
        genSeqRR (depth+1, mi+1, bi); // recurse on max - (middle + 1) thru biggest index
        genSeqRR (depth+1, si, mi-1); // recurse on min - smallest index thru (middle - 1)
     }
     break;

     case 0: // 1 elment
     {
        (void)m_tree->insertVal (si+1); // Note1

        // if(m_ss)
        *m_ss << "    rng:__1"
              << "   dpth:" << std::setw(3) << depth
              << "   iVal:" << std::setw(3) << si+1 << std::endl;
     }
     break;

     case 1: // 2 consecutive elements
     {
        // Note1,  Note2
        (void)m_tree->insertVal(bi+1);
        (void)m_tree->insertVal(si+1);

        // if(m_ss)
        *m_ss << "    rng:__2"
              << "   dpth:" << std::setw(3) << depth
              << "   iVal:" << std::setw(3) << si+1 << std::setw(3) << bi+1  << std::endl;
     }
     break;

     }// switch
  } // void genSeqRR()

范围 m_R = 20，

genSeqRR (1, 0, (m_R-1)); // start recursion over whole range

输出:

Anchor->showTallView()
                   '1' 
             '2' 
                         '3' 
                   '4' 
       '5' 
                   '6' 
             '7' 
                         '8' 
                   '9' 
 '10' 
                   '11' 
             '12' 
                         '13' 
                   '14' 
       '15' 
                         '16' 
                   '17' 
             '18' 
                         '19' 
                   '20' 

范围 m_R = 19，

genSeqRR (1, 0, (m_R-1)); // start recursion over whole range

输出:

Anchor->showTallView()
                   '1' 
             '2' 
                         '3' 
                   '4' 
       '5' 
                   '6' 
             '7' 
                         '8' 
                   '9' 
 '10' 
                   '11' 
             '12' 
                         '13' 
                   '14' 
       '15' 
                   '16' 
             '17' 
                         '18' 
                   '19' 

范围 m_R = 19，

Anchor->showTallView()
                   '1' 
             '2' 
                   '3' 
       '4' 
                   '5' 
             '6' 
                         '7' 
                   '8' 
 '9' 
                   '10' 
             '11' 
                         '12' 
                   '13' 
       '14' 
                   '15' 
             '16' 
                         '17' 
                   '18'