CF 109A.Lucky Sum of Digits(Java实现)

题目分析

        给定一个值，判断这个值能否被4和7组成，如果能就输出最小的组合。不能就输出-1。

思路分析

        由于是最小组合，即判断4能最多有多少个。但是如果一个值能完全被7整除，那就不需要4了，只用7组合的话位数会更短。(例如28总和，可以是4个7，也可以是7个4。如果完全判断4最多的情况位数反而更长了，所以要考虑能被7完全整除的情况)。此外由于组合可能会过长，用于输出答案的数据类型不能用数字表示，只能输出字符串，否则会由于溢出而显示错误答案。

代码

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s=sc.nextInt();//输入的值
		int n=0;//7的个数
		int m=isSum(s);//4的个数
		StringBuilder re=new StringBuilder();//用于输出答案
		if (m!=-1){//如果m为-1即不能够被4和7组成
			n=(s-4*m)/7;//计算7的个数
			for (int i = 0; i < m; i++) {//拼接4
				re.append(4);//拼接4
			}
			for (int i = 0; i < n; i++) {//拼接7
				re.append(7);//拼接7
			}

			System.out.println(re);//输出答案
		}else {
			System.out.println(-1);//如果不能组成则输出答案-1
		}


	}
	public static int isSum(int s) {//函数计算4的最多个数
		if (s % 7 == 0){//如果能被7完全整除
			return 0;//则4的个数为0
		}
		int maxM = s/ 4; // 计算 4 的最大可能值
		for (int m = 1; m <= maxM; m++) {//从1个开始循环判断
			int remaining = s - 4 * m;//剩下的数字
			if (remaining % 7 == 0) {//判断差值能否被7整除
				return m;//如果可以就输出此时4的个数
			}
		}
		return -1;//不能够组成
	}
}

        感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。