`
viking.liu
  • 浏览: 54538 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

用5,7,12加减运算,求最少步数得到任意数n

阅读更多
package www.viking.com.algorithm;

public class MinSteps {

	/**
	 * @param args
	 *            5,7,12加减运算表示任意n的最少个数
	 * 
	 *            也就是 5x+7y+12z=n
	 * 
	 *            求|x|+|y|+|z|的最小值
	 * 
	 *            方法一:动态规划的思想
	 * 
	 *            首先正数和负数的性质一样的,所以只考虑正数的情况
	 *            我们用f(n)表示所有的组合方式的5、7、12的最少的个数,因为组合方式有无限多种,我们只关心
	 *            最少的个数,要尽量向n减小的方向递归。 f(n)=min{f(n-5),f(n-7),f(n -12)}+1;
	 *            f(0)~f(12)是已知的
	 * 
	 *            动态规划的性能非常低,当n为3位数的时候就已经很慢了
	 * 
	 * 
	 *            方法二:另外一种更简单的方法,枚举法
	 * 
	 *            5x+7y+12z=n要使|x|+|y|+|z|的最小值,那么z要尽量的大, 所以x和y就有取值范围了 |x|<7,
	 *            |y|<12. 因为如果x>=7那么 5x=5(x-7)+5*7其中y=5,x-7+5肯定比x小,所以|x|一定小7
	 *            同理|y|<12。 用枚举法求出最少的|x|+|y|+|z|就可以了。
	 * 
	 * 
	 */
	public static void main(String[] args) {
		int n = -100;

		int step[] = { 5, 7, 12 };
		if (n < 0) {
			step[0] = -5;
			step[1] = -7;
			step[2] = -12;
		}
		int min1 = minSteps(n, step, "=" + n);
		int min2 = minSteps(n);
		System.out.println(min1 + " " + min2);
	}

	public static int minSteps(int n, int[] step, String path) {
		if (n == 5 || n == 7 || n == 12) {
			//System.out.println(n + path);
			return 1;
		} else if (n < 12 && n >= 0) {
			// 0=5-5
			// 1=5+5+5-7-7
			// 2=7-5
			// 3=5+5-7
			// 4=7+7-5-5
			// 6=7+7+7-5-5-5
			// 8=5+5+5-7
			// 9=7+7-5
			// 10=5+5
			// 11=7+7+7-5-5
			if (n == 0) {
				System.out.println("5-5" + path);
				return 2;
			}
			if (n == 1) {
				System.out.println("5+5+5-7-7" + path);
				return 5;
			}
			if (n == 2) {
				System.out.println("5-7" + path);
				return 2;
			}
			if (n == 3) {
				System.out.println("5+5-7" + path);
				return 3;
			}
			if (n == 4) {
				System.out.println("7+7-5-5" + path);
				return 4;
			}
			if (n == 6) {
				System.out.println("7+7+7-5-5-5" + path);
				return 6;
			}
			if (n == 8) {
				System.out.println("5+5+5-7" + path);
				return 4;
			}
			if (n == 9) {
				System.out.println("7+7-5" + path);
				return 3;
			}
			if (n == 10) {
				System.out.println("5+5" + path);
				return 3;
			}
			if (n == 11) {
				System.out.println("7+7+7-5-5" + path);
				return 5;
			}
		}
		int a[] = new int[3];
		a[0] = minSteps(n - step[0], step, "+" + step[0] + path);
		a[1] = minSteps(n - step[1], step, "+" + step[1] + path);
		a[2] = minSteps(n - step[2], step, "+" + step[2] + path);
		int min = a[0];
		for (int i = 1; i < a.length; i++) {
			if (a[i] != Integer.MAX_VALUE) {
				if (a[i] < min) {
					min = a[i];
				}
			}
		}
		if (min == Integer.MAX_VALUE) {
			return Integer.MAX_VALUE;
		}
		return min + 1;
	}

	public static int minSteps(int n) {
		if (n == 0) {
			System.out.println("0=(5-5)");
			return 2;
		}
		int z = 0;
		int min = Integer.MAX_VALUE;
		int num = 0;
		for (int x = -6; x < 7; x++) {
			for (int y = -11; y < 12; y++) {
				int rest = n - x * 5 - y * 7;
				if (rest % 12 == 0) {
					z = rest / 12;
					// x、y、z不能同时为负数
					// 因为只能做加减法,5、7、12都是整数,至少有一个数为整
					if (x > 0 || y > 0 || z > 0) {
						num = Math.abs(x) + Math.abs(y) + Math.abs(z);
						if (num < min && num != 0) {
							System.out.println(n + "=(" + x + "*5)+(" + y
									+ "*7)+(" + z + "*12)");
							min = num;
						}
					}
				}
			}
		}
		return min;
	}
}

分享到:
评论

相关推荐

    同个数加减乘除得到某数(不使用括号)

    标题“同个数加减乘除得到某数(不使用括号)”涉及到的是一个数学问题,探讨如何通过单一数字的不同算术运算(加法、减法、乘法、除法)来构造出目标数,而过程中不使用括号来改变运算顺序。这种问题在编程领域中有时...

    线性表设计100位以内的长整数加减运算的程序

    "线性表设计100位以内的长整数加减运算的程序" 知识点一:链表的基本结构和操作方法 在设计一个100位以内的长整数加减运算的程序时,使用链表来表示长整数是一个不错的选择。链表的基本结构包括节点和指针,节点中...

    加减运算器.docx

    在实验中,我们还了解了多功能加减运算电路的设计思路,了解了如何使用 HDL 描述方法设计多功能加减运算电路。我们填写了多功能加减运算电路模型,了解了各种运算对应的 M1、M0 及 Cin 取值。 在实验设计中,我们...

    表达式求值,加减乘除混合运算

    在本主题中,我们将深入探讨如何使用栈数据结构处理加减乘除四则混合运算,包括处理括号。栈是一种具有“后进先出”(LIFO)特性的数据结构,非常适合于解决此类问题。 首先,我们需要理解表达式的求值过程。对于...

    计算机组成原理之补码加减运算器

    它不仅涉及基本的加法器原理,还包括了补码加减运算和无符号数的加减运算,这些知识是构建计算机数字电路设计的基础。在这篇文章中,我们将详细解读计算机组成原理中的补码加减运算器,以及它在实现数字运算中的关键...

    实现任意大整数的加减运算

    实现任意大整数的加减运算! input(&num1, &num2); num3= sum(&num1, &num2); output(&num1); if(num2.flag==0) printf("%c", '+'); else printf("%c", '-'); output(&num2); printf("= "); if(num3....

    能够实现逻辑运算(逻辑非、逻辑加、逻辑乘、逻辑异)、定点整数的单符号位补码加减运算、定点整数的原码一位乘法运算和浮点数的加减运算

    能够实现逻辑运算(逻辑非、逻辑加、逻辑乘、逻辑异)、定点整数的单符号位补码加减运算、定点整数的原码一位乘法运算和浮点数的加减运算。

    一年级100以内加减混合运算口算题

    5. 一年级加减混合运算口算题的学习方法:一年级学生学习加减混合运算口算题时可以使用不同的学习方法,例如记忆法、计算法、解题法等等。 6. 加减混合运算口算题的类型:加减混合运算口算题可以分为不同的类型,...

    基于c51单片机简单的计算器程序,简易计算器设计两位数加减运算

    3. **运算逻辑**:实现基本的加减乘除运算,对于加减法,可以逐位进行;乘法和除法则需要更复杂的算法,例如二进制移位和逐位相加/减。 4. **显示驱动**:将运算结果显示在数码管上,需要配置P0、P1等端口作为数码管...

    汇编加减运算

    用于汇编语言中的加法和减法。通过减法可以得到正负值,及绝对值。

    C语言计算华容道移动最少步数

    《C语言实现华容道移动最少步数解析》 华容道,源于中国古代的棋类游戏,是一项极具挑战性的智力游戏。在这个问题中,我们关注的是如何利用C语言来计算解决华容道游戏的最少步数。C语言以其高效、简洁的特性,成为...

    大整数加减乘除运算

    以上就是大整数加减乘除运算的基本原理和实现方法,实际应用中还需结合特定的编程语言和库,例如Python的`decimal`模块、Java的`BigInteger`类等,它们提供了封装好的大整数操作接口,方便开发者使用。

    (完整版)有理数混合运算的整式的加减运算过关题.pdf

    这些题目涵盖了多个数学知识点,主要涉及有理数的混合运算和整式的加减运算,以及代数式的化简和求值。以下是对这些知识点的详细解释: 1. **有理数混合运算**:包括加、减、乘、除以及括号的使用。例如题目中的...

    《10以内数的加减混合运算》说课稿子.pdf

    《10以内数的加减混合运算》是青岛版一年级数学上册第三单元的重要内容,旨在帮助学生理解和掌握10以内数的加减混合运算的原理和方法。本节课的目标不仅是让学生掌握运算技能,更是要培养他们的逻辑思维能力和解决...

    数学表达式的求值算法实现(加减乘除及平方的混合运算)

    同时,`applyOperator`方法可能会处理遇到运算符时的操作,如根据运算符的类型进行加减乘除或平方运算。 此外,`Calculator`类可能还包含了一些辅助方法,如`isOperator`来判断字符是否为运算符,`getPriority`来...

    组成原理课程设计::功能:实现逻辑运算(逻辑非,逻辑加。。)定点整数的单符号位补码加减法,定点整数的原码一位乘法,浮点数的加减运算

    在加减运算中,需要对齐尾数的小数点,处理阶码的差异,并考虑下溢(underflow)和上溢(overflow)。下溢发生在两个非常接近的负数相加得到一个较小的负数,但超出了可表示的最小值;上溢则发生在两个较大数值相加...

    新人教七年级数学有理数的加减乘除乘方混合运算PPT课件.pptx

    新人教七年级数学有理数的加减乘除乘方混合运算PPT课件 以下是关于新人教七年级数学有理数的加减乘除乘方混合运算PPT课件的详细知识点: 一、有理数的混合运算顺序 在进行有理数的混合运算时,需要遵守一定的顺序...

    BigDecimal 加减乘除运算

    Java中BigInteger的数学运算,BigDecimal 加减乘除运算,Java在java.math包中提供的API类BigDecimal,用来对超过16位有效位的数进行精确的运算。双精度浮点型变量double可以处理16位有效数。在实际应用中,需要对更大...

Global site tag (gtag.js) - Google Analytics