关于算法的题目整数分解

lw2001

假设有一类数，它只由0 1 构成，例如10 ，101，0，1，111这种，
给定一个数，如何找到能构成的的最少的这类数的数量，
举个例子，0 只需要一个 0 即可得到
30只需要10+10+10三个数即可得到
那应该怎么找出这些数的数量呢？




我自己的想法是 从大到小开始找这类数，但是比如说30，在找的过程中就可能会出现说 先找到一个 11，那之后就只剩9了，算起来就是 11个数 ，但事实上只需要三个10就可以了，
同样如果说得到一个31只需要11 + 10 +10即可，但是我的算法他会变成 11 +11+ 9*1共12个数，我想问一下大家会怎么做这个题。

人生苦短丶

不懂你是想找什么，30可以30个1 也可以3个10 也可以1个11 ，19个1，你是想找最少数量吗

lw2001

人生苦短丶 发表于 2019-12-6 17:13
不懂你是想找什么，30可以30个1 也可以3个10 也可以1个11 ，19个1，你是想找最少数量吗

是的，需要找最少数量的这类数

殊_途

这是你想要的答案吗？

lw2001

殊_途 发表于 2019-12-6 21:49
这是你想要的答案吗？

是的，就是这种，想请教一下大佬实现的大致方法是什么，我写的想的办法总是解决不了会多选一些比较大的数然后就必须用更多的一些小一些再凑起来，最后n总是求不对。

殊_途

lw2001 发表于 2019-12-7 00:20
是的，就是这种，想请教一下大佬实现的大致方法是什么，我写的想的办法总是解决不了会多选一些比较大的数 ...

这个问题还是很简单的（我不是大佬，不知道还有没有更好的算法），问题的关键在于这类数是有规律可循的，话不多说直接上代码

[Java] 纯文本查看 复制代码

package com.lpc.pack;

import java.util.Scanner;

public class ResolveNumber {
	public static void main(String[] args) {
		System.out.println("请输入一个正整数：");
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		sc.close();
		int length = String.valueOf(num).length(); // 整数的位数

		int[] place = new int[length]; // 数量级
		for (int i = 0; i < length; i++) {
			place[length - 1 - i] = (int) Math.pow(10, i);
		}

		int[] count = new int[length]; // 位对应的数
		int temp = num;
		for (int i = 0; i < length; i++) {
			count[i] = temp / place[i];
			temp -= count[i] * place[i];
		}

		System.out.println(num + "可分解为：");
		int min;
		int originalValue;
		for (int i = 0; i < length; i++) {
			originalValue = place[i];
			while (count[i] != 0) {
				min = findMin(count, i); // 位对应的数的最小值
				count[i] = count[i] - min;
				for (int j = i + 1; j < length; j++) {
					if (count[j] == 0) {
						continue;
					}
					count[j] = count[j] - min;
					place[i] += place[j];
				}
				System.out.println(min + "个：" + place[i]);
				place[i] = originalValue;
			}
		}
	}

	private static int findMin(int[] count, int m) {
		int min = count[m];
		for (int i = m + 1; i < count.length; i++) {
			if (min > count[i] && count[i] != 0) {
				min = count[i];
			}
		}
		return min;
	}
}

xuyincheng

[Python] 纯文本查看 复制代码

def calc(num):
    if(num == 0):
        return
    s = str(num)
    temp = ""
    smin = 9
    for i in range(len(s)):
        item = int(s[i])
        if item > 0:
            temp = temp + "1"
            if(smin > item):
                smin = item
        else:
            temp = temp + "0"
    print("%d个:"%smin + temp)
    calc(num - smin * int(temp))

殊_途

xuyincheng 发表于 2019-12-7 09:30
[mw_shl_code=python,true]def calc(num):
    if(num == 0):
        return

牛掰啊，这就是大神和我小白的区别

lw2001

谢谢大佬们我明白自己的错误在什么地方了，非常感谢