C递归中的因式分解

Question

我被要求用 c（无循环）编写一个 void 函数，它得到一个偶数（比如说 80），并像这样打印它 2*2*5*2*2 如您所见，结果是 80 笑。在 2 个数字之间你需要打印“*”，而奇数（对于我的例子，5）你需要在中间打印它，或者如果数字中有奇数“2”，假设你是 96需要像 that:2*2*2*3*2*2 这样打印如果给定的数字是奇数，则 return 该数字。我不仅希望得到答案，还希望得到您在开始编码之前 "think" 的方式。这是我到目前为止得到的

if(n%4==0)
{
  printf("2*");
  PrintTwos(n/4);
  return;
 }
 if(n%2==0)
 {
 printf("*2");
 PrintTwos(n/2);
  return;
  }
   printf("%d",n);

Answer 1

这是一些伪代码：

func(nbr)
  isOdd(nbr)         // recursive stop condition
    print nbr
    return

  evenNbr = findFirstEven(nbr)  //return the shortest even number from nbr
  print evenNbr
  func(nbr / evenNbr)

我没有为 * 打印添加逻辑，因为我相信你可以自己想出来。一个案例会破坏该伪代码，但这是帮助您思考递归函数应该做什么的良好开端。

编辑以下评论：（不完整：此处缺少中间的奇数）

int findFirstEven(nbr, i) {
    if (nbr%i != 0)
      return findFirstEven(nbr, i++);
    return i;
}

int primefact(int n)
{
    int i=2;
    i = findFirstEven(n, i);

    printf("%d*", i);
    if(n==i)
        printf("1");
        return 0;
    else
        primefact(n/i);
}

（未测试）

Answer 2

你需要将 2 分成两半，所以你需要在递归步骤之前从数字中删除 two - 否则递归步骤必须知道它有多深避免在左侧打印太多双。
当然你必须验证是否真的有两个二！

所以：

void PrintTwosInNumber(unsigned n)
{
    if(n % 4 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/4);
        printf("*2");
    }
    else if(n % 2 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/2);
    }
    else
        printf("%u", n);
}

您可以使用

保存最后的递归步骤

void PrintTwosInNumber(unsigned n)
{
    if(n % 4 == 0)
    {
        printf("2*");
        PrintTwosInNumber(n/4);
        printf("*2");
    }
    else if(n % 2 == 0)
        printf("2*%u", n/2);
    else
        printf("%u", n);
}

编辑：

请注意函数将陷入 n==0 的无限递归 - 零可以被 2 无限整除。但是，零不能表示为任意数量的 2 和某个奇数的乘积，因此它超出了这个问题的范围。
无论如何，如果它是一个 真正的 编程任务，那么应该考虑到这种特殊情况并添加一个保护 if(n==0) return; 分支，只是为了在调用者通过一个参数值错误。

C递归中的因式分解

Factorization in C-Recursion

c

recursion

factorization