Tag - 分治算法

本文主要是介绍Tag - 分治算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基础知识去看B站视频

说明：
1、分治与递归的区别
分治法是指一种算法（分而治之，逐步细化地处理）；
递归是指一种实现（函数中调用自身）

分治法也可以不用递归实现，比如自己用一个堆栈去模拟。

总之前者是思路，后者是做法。
我们做家务，也可以用分治法，我们管理一个组织，也可以用分治法，但是这就和编程完全无关了。
2、分治算法的应用：
快速排序等

关于视频中的例题，我的代码：

#include <iostream>
using namespace std;
int solve(int coin[],int low,int high){
    int sumLeft = 0,sumRight = 0,sumMid = 0;
    int ans;//这里写ans是为了递归的最终（最外层函数）返回
    if(low + 1 == high){
        //说明分治到了最后还剩两个数组的元素
        if(coin[low] > coin[high]){
            ans = high + 1;
            return ans;
        }else{
            ans = low + 1;
            return ans;
        }
    }else
    if((high - low + 1) % 2 == 0){
        //说明元素数是偶数，分成左面一半和右面一半
        //int sumLeft = 0,sumRight = 0;
        for(int i = low;i <= low + (high - low) / 2;i++){
            sumLeft = sumLeft + coin[i];
        }
        for(int i = low + (high - low) / 2 + 1;i <= high;i++){
            sumRight = sumRight + coin[i];
        }
        if(sumLeft < sumRight){
            ans = solve(coin,low,low + (high - low) / 2);
            return ans;
        }else
        if(sumLeft > sumRight){
            ans = solve(coin,low + (high - low) / 2 + 1,high);
            return ans;
        }else{

        }
    }else{
        //说明元素个数为奇数
         
        for(int i = low; i <= low + (high - low) / 2 - 1; i++){
            sumLeft = sumLeft + coin[i];
        }
        for(int i = low + (high - low) / 2 + 1; i <= high; i++){
            sumRight = sumRight + coin[i];
        }
        sumMid = coin[low + (high - low) / 2];
        if(sumLeft < sumRight){
            ans = solve(coin,low,low + (high - low) / 2 - 1);
            return ans;
        }else  
        if(sumLeft > sumRight){
            ans = solve(coin,low + (high - low) / 2 + 1,high);
            return ans;
        }else{
            
        }
        if(sumRight + sumMid == sumLeft + sumMid){
            ans = low + (high - low) / 2 + 1;
            return ans;
        }

    }
    return ans;
}


int main(){
    int coinNum = 0;
    cout << "请输入硬币数" << endl;
    cin >> coinNum;
    int coin[coinNum];
    cout << "请依次输入" << coinNum << "个硬币的每个硬币的重量:" << endl;
    for(int i = 0;i < coinNum;i++){
        cin >> coin[i];
    }
    cout << "不合格的那枚硬币是第" << solve(coin,0,coinNum - 1) << "枚硬币" << endl; 
    
}

这篇关于Tag - 分治算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！