【基础算法】分治算法 & C++实现

简介: 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。下面的硬币问题就是分治算法的一种典型算法题。

简要介绍:


       分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。下面的硬币问题就是分治算法的一种典型算法题。


●硬币问题


       在下面我们将硬币分为1和0两个值,1为真硬币,0为假硬币。找偶数枚硬币和奇数枚硬币将其随机排成一列,其中有一个假硬币,用分治算法寻找出这枚假硬币所在的位置。如下两图所示:


当硬币个数为偶数时(10枚):

a97c4e4ce3335ad80ea6256860d479d1_c98c1b0a6ad84168a195efba835a4dbd.png

当硬币个数为奇数时(13枚):

1ac08754c04a78c002bd62e4dd1a5cd2_9e0abdc0a8364362a112b82553da0221.png

代码实现:

#include<iostream>
using namespace std;
#define maxsize 20
class fenzhi {
public:
  int falsecoin(int low, int high);
  void showresult();
  int num;
  int coin[maxsize];
  int result;
};
int fenzhi::falsecoin(int low, int high)
{
  int sum1=0;
  int sum2=0;
  int sum3=0;
  if (low + 1 == high)  //只有两枚硬币
  {
  if (coin[low] < coin[high])
  {
    result = low + 1;
    return result;
  }
  else
  {
    result = high + 1;
    return result;
  }
  } 
  //分治算法
  if((high-low+1)%2==0)  //n是偶数
  { 
  for (int i = low; i <= low+(high-low)/2; i++)
  {
    sum1 += coin[i];//前半段和
  }
  for (int j = low + (high - low) / 2+1; j <= high; j++)
  {
    sum2 += coin[j];//后半段和
  }
  if (sum1 > sum2)
  {
    result = falsecoin(low + (high - low) / 2 + 1, high); //递推后半段
    return result;
  }
  else if(sum1 < sum2)
  {
    result = falsecoin(low, low + (high - low) / 2); //递推前半段
    return result;
  }
  }
  else  //n是奇数
  {
  for (int i = low;i<=low+(high-low)/2-1;i++)
  {
    sum1 += coin[i];   //中位数的前半段和
  }
  for (int j = low + (high - low) / 2+1; j <= high; j++)
  {
    sum2 += coin[j];   //中位数的后半段和
  }
  sum3 = coin[low + (high - low) / 2];   //中位数
  if (sum1 > sum2)      //前半段和大于后半段和
  {
    result = falsecoin(low + (high - low) / 2 + 1, high);//递推后半段
    return result;
  }
  else if (sum1 < sum2)   //前半段和小于后半段和
  {
    result = falsecoin(low, low + (high - low) / 2 - 1);//递推前半段
    return result;
  }
  if (sum1 + sum3 == sum2 + sum3)    //前半段和加中位数等于后半段和加中位数,所以中位数为目标寻找值
  {
    result = low + (high - low) / 2+1;
    return result;
  }
  }
}
void fenzhi::showresult()
{
  cout << "假币所在的位置:" << this->result << endl;
}
void text()
{
  fenzhi fz;
  cout << "输入硬币的总数目:" << endl;
  cin >> fz.num;
  cout << "请输入硬币的真假(1真/0假):" << endl;
  for (int i = 0; i < fz.num; i++)
  {
  cin >> fz.coin[i];
  }
  fz.falsecoin(0, fz.num - 1);
  fz.showresult();
}
int main()
{
  text();
}

ae37b88c97841913d7aeef0503643991_ad8961e3d0a74333bfba4bc5baec10c9.png

目录
相关文章
|
24天前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
288 0
高精度算法(加、减、乘、除,使用c++实现)
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
1月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
1月前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)