分治算法

作者: FORGET_静哥哥 | 来源:发表于2019-02-15 09:28 被阅读0次


package com.xj.www.algo;
import java.util.Scanner;
/**
 * 分治算法
 *
 * @author xiongjing
 *
 */
public class DivideTest {
      static int FalseCoin(int coin[], int low, int high) {
            int i, sum1, sum2, sum3;
            int re = 0;
            sum1 = sum2 = sum3 = 0;
            // 算法具体实现
            // 判断high == 1的情况
            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 += coin[i];
                  }
                  for (i = low + (high - low) / 2 + 1; i <= high; i++) {
                        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 += coin[i];
                  }
                  for (i = low + (high - low) / 2 + 1; i <= high; i++) {
                        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);
                  } else {
                  }
                  if (sum1 + sum3 == sum2 + sum3) {
                        re = low + (high - low) / 2 + 1;
                        return re;
                  }
            }
            return re;
      }
      // 方法主入口
      public static void main(String[] args) {
            int i, n;
            int weizhi;
            System.out.println("分治算法求解假币问题!");
            System.out.print("请输入硬币总的个数:");
            @SuppressWarnings("resource")
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            System.out.print("请输入硬币的真假:");
            int[] coin = new int[n];
            for (i = 0; i < n; i++) {
                  coin[i] = sc.nextInt();
            }
            weizhi = FalseCoin(coin, 0, n - 1);
            System.out.println("在上述" + n + "个硬币中,第" + weizhi + "个硬币是假的!");
      }
}

相关文章

  • 分治算法

    文章结构 如何理解分治算法 分治算法应用举例 1. 如何理解分治算法 1.1 分治算法的核心思想 分治算法的核心思...

  • 算法导论第2.3章 - 分治算法

    分治算法 递归:算法一次或多次递归地调用其自身已解决紧密相关的若干子问题。这些算法遵循分治法的思想。 分治算法三个...

  • 从分治算法到 MapReduce

    从分治算法说起 要说 MapReduce 就不得不说分治算法,而分治算法其实说白了,就是四个字 分而治之 。其实就...

  • Leetcode-Java(二十五)

    241. Different Ways to Add Parentheses 采用分治算法,分治算法的基本思想是将...

  • 09《算法入门教程》分治算法

    1. 前言 本节内容是分治算法系列之一:分治算法的介绍,主要介绍了分治算法的定义及基本思想和实现策略,然后我们介绍...

  • 分治算法

    理解分治算法 分而治之

  • 分治算法

    分治是一种思想体现,就是把一个大的问题分为若干个子问题,这些子问题相互独立且与原问题性质相同然后在子问题继续向下分...

  • 分治算法

    分治算法字面意思就是将一个复杂的数据进行分开计算,分治 的策略就是: 一个分治法将规模为n的问题分成k个规模为n/...

  • 分治算法

    http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741...

  • 分治算法

    分冶算法的基本思想是将原问题分解为几个规模较小的但类似原问题的子问题,递归地求解这些了问题,然后再合并这些子问题的...

网友评论

    本文标题:分治算法

    本文链接:https://www.haomeiwen.com/subject/ovzueqtx.html