【数字涂色 100分（python、java、c++、js、c）】
题目
疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。黑板上已经写上了N个正整数，同学们需要给这每个数分别上一种颜色。为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这N个数进行上色
输入描述
第一行有一个正整数N，其中。
第二行有N个int型数(保证输入数据在[1,100]范围中)，表示黑板上各个正整数的值
输出描述
输出只有一个整数，为最少需要的颜色种数
用例
用例一：
输入：
3 2 4 6
输出：
1
用例二：
输入：
4
2 3 4 9
输出：
2
python解法
解题思路：
本程序的目标是计算数组可以被分成的最少颜色组数，其中：
任何一个颜色组中的所有数字，都不能是另一个数字的倍数。需要最少的颜色数，即尽可能少的组数。解题步骤读取输入
n：整数，表示数组元素个数。arr：包含 n 个整数的列表。递归划分颜色组 find_colors(nums)
排序数组：先对 nums 进行升序排序，确保最小数 base 先被选中。选取最小数 base 作为第一个颜色组的基础：将 base 作为当前组的代表。过滤掉 nums 中所有 base 的倍数，得到 filtered。递归调用 find_colors(filtered) 计算剩余数组的最小颜色组数。最终返回 1 + find_colors(filtered)，其中 1 代表当前颜色组，find_colors(filtered) 递归计算剩余部分的颜色组数。
# 读取输入 n = int(input()) # 读取数组大小 arr = list(map(int, input().split())) # 读取数组元素 # 计算最少颜色组数的函数 def find_colors(nums): if not nums: # 递归终止条件：如果数组为空，返回0 return 0 nums.sort() # 排序数组，确保最小的数优先处理 base = nums[0] # 选取最小的数作为当前颜色组的基准 # 过滤掉所有是 base 倍数的数，剩余的数进入下一个递归 filtered = [num for num in nums if num % base != 0] # 1 (当前组) + 递归计算剩余数的颜色组数 return 1 + find_colors(filtered) # 输出最少颜色组数 print(find_colors(arr))java解法
解题思路
本程序的目标是计算数组可以被分成的最少颜色组数，其中：
任何一个颜色组中的所有数字，都不能是另一个数字的倍数。需要最少的颜色数，即尽可能少的组数。解题步骤读取输入
读取整数 n，表示数组的元素个数。读取 n 个整数，并存入 numbers 数组。计算最少颜色组数 calculateMinColors(n, numbers)
排序 numbers：先对数组进行升序排序，确保较小的数先被考虑。创建布尔数组 used[]：used[i] == true 表示 numbers[i] 已经被归类到某个颜色组，不需要再考虑。遍历 numbers 并标记倍数：如果 numbers[i] 没有被使用，增加颜色组 colorCount。遍历 numbers[j]（j > i），如果 numbers[j] 是 numbers[i] 的倍数，则将其标记为已使用 used[j] = true。返回 colorCount 作为最少颜色组数
统计出最小的颜色组数，并返回
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数组大小 int n = Integer.parseInt(scanner.nextLine()); // 读取数组元素并转换为整数数组 int[] numbers = Arrays.stream(scanner.nextLine().split(" ")) .mapToInt(Integer::parseInt) .toArray(); // 计算最少颜色组数并输出 System.out.println(calculateMinColors(n, numbers)); } public static int calculateMinColors(int n, int[] numbers) { Arrays.sort(numbers); // 对数组进行排序，确保较小的数先处理 int colorCount = 0; // 记录最少颜色组数 boolean[] used = new boolean[n]; // 标记数组，记录哪些数字已归类 // 遍历所有数字，确定颜色组 for (int i = 0; i < n; i++) { if (used[i]) continue; // 如果当前数字已归类，则跳过 colorCount++; // 发现一个新的颜色组 // 遍历剩余的数字，标记所有当前数字的倍数 for (int j = i + 1; j < n; j++) { if (!used[j] && numbers[j] % numbers[i] == 0) { used[j] = true; // 标记该数字已归类 } } } return colorCount; // 返回最少颜色组数 } }
