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

张育玮

如图

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-5-8 12:40:13

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

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

据我了解：

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

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

跳转到最佳答案楼层

wp231957

这个对吗？？？

1. def foo(i):
   
2.   count=0
   
3.   while i>1:
   
4.     if i%2==0:
   
5.       i=i//2-1
   
6.     else:
   
7.       i=(i-1)//2  
   
8.     count+=1
   
9.   return count   
   
10. 
    
11. for x in range(16,31):
    
12.     print("%d 需要分解%d次"%(x,foo(x)))     

复制代码

张育玮

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

要是C++

傻眼貓咪

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

1. #include <iostream>
   
2. 
   
3. int foo(int N) {
   
4.         int res = 0;
   
5.         for (; N > 1; N = !(N & 1) ? (N >> 1) - 1 : (N - 1) >> 1, res++) { ; }
   
6.         return res;
   
7. }
   
8. 
   
9. int main(void) {
   
10.         std::cout << foo(16);
    
11.         return 0;
    
12. }

复制代码

张育玮

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

要用分治呀

wp231957

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

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

1. #include <stdio.h>
   
2. 
   
3. int  foo(long long int i)
   
4. {
   
5.     int count=0;
   
6.     while(i>1)
   
7.     {
   
8.         if (i%2==0) i=i/2-1;
   
9.         else i=(i-1)/2;
   
10.         count++;
    
11.     }
    
12.     return count;
    
13. }
    
14. 
    
15. int main()
    
16. {
    
17.     for (int i=16;i<=31;i++)
    
18.         printf("%d 需要分解%d次  \n",i,foo(i)) ;   
    
19.     return 0;         
    
20. }
    

复制代码

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 取商和取模难道不算是分治法吗？