您现在的位置是:首页 > 正文

分治算法

2024-04-01 01:39:46阅读 3

一.分治算法的基本思想
分治算法的基本思想是将一个计算复杂的问题分为规模较小、计算简单的小问题求解,然后综合各个小问题,得到最终的答案。大致执行的流程如下:
1.对于一个规模为N的问题,若该问题比较容易解决(比如规模N较小),则直接解决;否则执行下面的步骤。
2.将该问题分解为M的个规模的小问题,这些子问题相互独立,
并且与原问题的形式相同。
3.递归地解这些子问题
4.然后,将各个子问题的解合并得到原问题的解。
使用分治算法需要待求解问题能够转化为若干个小规模的相同问题,通过逐步的划分,能够达到一个易于求解的阶段而直接求解。然后,程序中可以使用递归算法来进行求解。

典型实例
一个袋子里有10个硬币,其中有一枚是假的,并且假币和真币一模一样,肉眼很难分辨出来,目前知道假币比真币的重量轻一点。请问怎么区分哪枚硬币是假币?
1.分析
采用递归分治算法的思想来解决这个问题,大致分析步骤如下:
1)首先为每一枚硬币编号,然后将所有的硬币等分为两份,放在天平的两边。这样就将区分10枚硬币的问题,变为区别两堆硬币的问题。
2)因为假币的重量轻,因此天平较轻的一侧中一定包含假币。
3)再将较轻的一侧的硬币等分为两份,重复上述的做法。
4)直到剩下两枚硬币,可用天平直接找出假币。
2.参考代码

import java.util.Scanner;

public class Divide_conquer {
	static final int maxnum=10;
	static int FalseCoin(int coin[],int low,int high) {
		int i,sum1,sum2,sum3;
		int re = 0;
		sum1=sum2=sum3=0;
		if(low+1==high) {
			if(coin[low]<coin[high]) {
				re=low+1;
				return re;
			}else {
				re=high+1;
				return re;
			}				
		}
		if((high-low+1)%2==0) {
			for(i=low;i<=low+(high-low) / 2;i++) {
				sum1=sum1+coin[i];
			}
			for(i=low+(high-low) / 2;i<=high;i++) {
				sum2=sum2+coin[i];
			}
			if(sum1>sum2) {
				re=FalseCoin(coin, low+(high-low) / 2+1, high);
				return re;
			}else if(sum1 < sum2) {
				re=FalseCoin(coin, low, low+(high-low) /2);
				return re;
			}else {
				
			}
		}else {
			for(i=low;i<=low+(high-low /2-1);i++) {
				sum1=sum1+coin[i];
			}
			for(i=low+(high-low) / 2+1;i<=high;i++) {
				sum2=sum2 + coin[i];
			}
			sum3=coin[low+(high-low)/2];
			if(sum1>sum2) {
				re=FalseCoin(coin, low+(high-low) / 2+1, high);
				return re;
			}else if(sum1 < sum2){
				re=FalseCoin(coin, low, low+(high-low) / 2-1);
				return re;
			}else {
				
			}
			if(sum1+sum3==sum2+sum3) {
				re=low+(high-low) /2+1;
				return re;
			}
		}
		return re;	
	}
	public static void main(String[] args) {
		int [] coin = new int[maxnum];
		int i,n;
		int location;
		System.out.println("分治算法求假硬币问题!");
		System.out.println("输入硬币的总的个数:");
		Scanner input = new Scanner(System.in);
		n=input.nextInt();
		System.out.println("请输入硬币的真假:");
		for(i=0;i<n;i++) {
			coin[i]=input.nextInt();
		}
		location=FalseCoin(coin, 0, n-1);
		System.out.println("在上述"+maxnum+"个硬币中,第"+location+"个硬币是假的!");
	}

}


3.结果展示
在这里插入图片描述

网站文章

  • 【C语言】分支语句与循环语句

    【C语言】分支语句与循环语句

    前言 本篇记得是C语言中的分支和循环语句。 分支语句ifelse语句、switch语句 循环语句while循环、for循环、do while循环 语句 C语言中由一个分号;隔开的就是一条语句。比如: ...

    2024-04-01 01:39:41
  • nginx源码分析—reuseport的使用

    本文主要介绍nginx中reuseport的使用,文中代码较多,阅读本文需要读者对nginx的事件模块以及listen配置过程有了解。 由于nginx比较复杂,且作者对nginx的理解有限,文章难免存...

    2024-04-01 01:39:16
  • QNX中mmap_device_io() 和 mmap_device_memory()函数

    来源于QNX IDE 1、mmap_device_io() 1)函数定义 #include #include uintptr_t mmap_device_io( size_t len, uint64_t io ); len The number of bytes of device I/O memory that you want to access. It can&#39;..

    2024-04-01 01:39:08
  • 位运算的一些技巧

    位运算的一些技巧

    1. 两个数异或:相当于每一位相加,而不考虑进位; 2. 两个数相与,并左移一位:相当于求得进位; 3. 一个数n与其减一的数相与(即n&amp;(n-1)),等价于去掉最左边的1 如n=10二进制为1010,n&amp;(n-1)=1000 应用以上技巧可以解决一些算法题: 下面是剑指offer上的一道题: class Solution { public: int Add(int n...

    2024-04-01 01:39:00
  • 互联互通、电子病历、智慧服务、智慧管理、公立医院绩效考核的5项测评

    互联互通、电子病历、智慧服务、智慧管理、公立医院绩效考核的5项测评

    互联互通、电子病历、智慧服务、智慧管理、公立医院绩效考核的5项测评

    2024-04-01 01:38:35
  • C++ 笔记 shared_from_this()的原理与使用

    shared_from_this()的用途 enable_shared_from_this是一个模板类,定义于头文件,其原型为: template&lt; class T &gt; class enable_shared_from_this; std::enable_shared_from_this 能让一个对象(假设其名为 t ,且已被一个 st...

    2024-04-01 01:38:27
  • Windows10登录不上Micrsoft账户,解决办法

    Windows10登录不上Micrsoft账户,解决办法

    原文 1 问题 在登录Windows账户时,出现了以下错误: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GJIEFAWY-1641732153972)(https:...

    2024-04-01 01:38:16
  • HTML分组标签fieldset

    HTML分组标签fieldset

    1、标签: 2、作用: (1)可以将表单内的相关元素分组; (2)会在相关表单元素周围绘制边框; 3、语法 组的名字 内容 4、案例 个人信息: 姓名:

    2024-04-01 01:37:51
  • oracle adf取不到表中的控件,[导入]使用oracle adf 的一点经验(一)

    目前使用oracle adf 框架 10.1.3 版本1 adf 的源代码 (交付给apache 的)2. 其实我把 adf-faces-api adf-faces-impl.jar 用jad 解码出...

    2024-04-01 01:37:43
  • 关于不修改android:debuggable进行动态调试

    有时候手动修改导致程序再打包失败其他的方法又局限性,所以采用buildprop插件来完成https://repo.xposed.info/module/com.jecelyin.buildprop转载于:https://blog.51cto.com/13652962/2358860...

    2024-04-01 01:37:36