[已解决]求助，这道分治怎么做？

张育玮

如图

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-5-8 12:40:13

张育玮 发表于 2022-5-8 10:39
要用分治呀

请问楼主想要怎样的分治法？有例子吗？

据我了解：

分治法（Divide and conquer）是建基于多项分支递回的一种很重要的演算法范式。字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

好奇问一下...
如题：要求输出最少比较次数，其实就是分治法的递数（层），但不要回数，2楼大佬虽然不知道什么是分治法，但已经间接用了分治法原理运算了不是吗？对除于 2 取商和取模难道不算是分治法吗？

跳转到最佳答案楼层

wp231957

这个对吗？？？

def foo(i):
  count=0
  while i>1:
    if i%2==0:
      i=i//2-1
    else:
      i=(i-1)//2  
    count+=1
  return count    

for x in range(16,31):
    print("%d 需要分解%d次"%(x,foo(x)))     

张育玮

wp231957 发表于 2022-5-8 10:22
这个对吗？？？

要是C++

傻眼貓咪

借花献佛，运用2楼代码改成 C++：

#include <iostream>

int foo(int N) {
        int res = 0;
        for (; N > 1; N = !(N & 1) ? (N >> 1) - 1 : (N - 1) >> 1, res++) { ; }
        return res;
}

int main(void) {
        std::cout << foo(16);
        return 0;
}

张育玮

傻眼貓咪 发表于 2022-5-8 10:34
借花献佛，运用2楼代码改成 C++：

要用分治呀

wp231957

张育玮 发表于 2022-5-8 10:39
要用分治呀

不知道啥是 分治     只是核心代码 给你了   剩下的你自己琢磨吧
c++不会啊

#include <stdio.h>

int  foo(long long int i)
{
    int count=0;
    while(i>1)
    {
        if (i%2==0) i=i/2-1;
        else i=(i-1)/2;
        count++;
    }
    return count;
}
 
int main()
{
    for (int i=16;i<=31;i++)
        printf("%d 需要分解%d次  \n",i,foo(i)) ;   
    return 0;         
} 

wp231957

傻眼貓咪 发表于 2022-5-8 10:34
借花献佛，运用2楼代码改成 C++：

厉害，但不知道这个思路是否对

张育玮

wp231957 发表于 2022-5-8 10:41
不知道啥是 分治     只是核心代码 给你了   剩下的你自己琢磨吧
c++不会啊

谢谢，但这个不行哦

wp231957

张育玮 发表于 2022-5-8 10:50
谢谢，但这个不行哦

把循环测试改成手工输入数据？？

张育玮

wp231957 发表于 2022-5-8 10:51
把循环测试改成手工输入数据？？

no

傻眼貓咪

张育玮 发表于 2022-5-8 10:39
要用分治呀

请问楼主想要怎样的分治法？有例子吗？

据我了解：

分治法（Divide and conquer）是建基于多项分支递回的一种很重要的演算法范式。字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

好奇问一下...
如题：要求输出最少比较次数，其实就是分治法的递数（层），但不要回数，2楼大佬虽然不知道什么是分治法，但已经间接用了分治法原理运算了不是吗？对除于 2 取商和取模难道不算是分治法吗？