C编程：17个自然数分为n组每组数的和之差最小
C语言编程的问题
编程要求：17个自然数（这17个数由用户输入）分成n组（n由用户输入），每组数的和相近，输出的是分好的组
举例如图片所示
这个问题是 NP Hard 问题，通俗一点说，就是要么只能穷举，要么就是只能寻找近似最优解
好在17个数字也不是很多，C(17,n)，当n=8的时候，可能性最多，也就只有24000多种。你穷举下即可。
穷举所有
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于排序
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int numbers[17];
int n, sum = 0;
printf("请输入17个自然数：\n");
for (int i = 0; i < 17; ++i) {
scanf("%d", &numbers[i]);
sum += numbers[i];
}
printf("请输入分成多少组：\n");
scanf("%d", &n);
int targetSum = sum / n;
// 排序输入数组
qsort(numbers, 17, sizeof(int), compare);
int groups[n][17]; // 存储每组的数
int sums[n]; // 存储每组的和
for (int i = 0; i < n; ++i) {
sums[i] = 0;
}
int currentGroup = 0;
for (int i = 16; i >= 0; --i) {
groups[currentGroup][sums[currentGroup]] = numbers[i];
sums[currentGroup] += numbers[i];
currentGroup = (currentGroup + 1) % n; // 轮流分配给每组
}
printf("分好的组为：\n");
for (int i = 0; i < n; ++i) {
printf("组 %d：", i + 1);
for (int j = 0; j < sums[i]; ++j) {
printf(" %d", groups[i][j]);
}
printf("\n");
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_NUMBERS 17
void divideIntoGroups(int numbers[], int n, int k, int groups[], int currentGroup, int currentSum) {
if (currentGroup == k) {
for (int i = 0; i < k; i++) {
printf("Group %d: ", i + 1);
for (int j = 0; j < groups[i]; j++) {
printf("%d ", numbers[j + currentSum]);
}
printf("\n");
currentSum += groups[i];
}
printf("\n");
} else {
for (int i = 1; i <= n - currentSum - (k - currentGroup - 1); i++) {
groups[currentGroup] = i;
divideIntoGroups(numbers, n, k, groups, currentGroup + 1, currentSum + i);
}
}
}
int main() {
int numbers[MAX_NUMBERS];
int n, k;
printf("Enter the value of n (number of elements): ");
scanf("%d", &n);
if (n > MAX_NUMBERS) {
printf("Maximum allowed number of elements is %d.\n", MAX_NUMBERS);
return 1;
}
printf("Enter %d numbers: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
printf("Enter the value of k (number of groups): ");
scanf("%d", &k);
int groups[k];
divideIntoGroups(numbers, n, k, groups, 0, 0);
return 0;
}
【以下回答由 GPT 生成】
我会首先进行以下步骤来解决这个问题：
步骤 1: 确定输入和输出 - 输入：17个自然数和n的值 - 输出：每组的数之和相差最小的分组方案
步骤 2: 创建一个函数来计算每组的和之差 - 创建一个函数calculateDifference来计算每组的和之差 - 函数将会接收一个数组和数组的长度作为参数
步骤 3: 生成所有可能的组合 - 创建一个函数generateCombinations来生成给定数目组合的所有可能情况 - 这个函数将使用递归来生成组合，每次迭代时，从数组中选择一个数并将其添加到当前组中，然后递归调用生成下一个数目组合 - 如果组合的数目等于目标数目n，将调用calculateDifference函数计算该组合的和之差，并将其保存到一个结果列表中
步骤 4: 找到和之差最小的组合 - 创建一个函数findMinimumDifference来找到和之差最小的组合 - 函数将会接收一个结果列表作为参数，并计算并返回其中和之差最小的组合
步骤 5: 编写主程序 - 在主程序中，接收用户输入的17个自然数和n的值 - 调用generateCombinations函数生成所有可能的组合 - 调用findMinimumDifference函数找到和之差最小的组合 - 输出最佳的分组方案
下面是使用C语言编写以上步骤的示例代码：
#include <stdio.h>
int calculateDifference(int arr[], int len) {
int sum = 0;
for(int i = 0; i < len; i++) {
sum += arr[i];
}
return sum;
}
void generateCombinations(int arr[], int len, int group[], int groupLen, int target, int start, int results[], int *resultIndex) {
if(groupLen == target) {
int difference = calculateDifference(group, groupLen);
results[*resultIndex] = difference;
(*resultIndex)++;
return;
}
for(int i = start; i < len; i++) {
group[groupLen] = arr[i];
generateCombinations(arr, len, group, groupLen + 1, target, i + 1, results, resultIndex);
}
}
int findMinimumDifference(int results[], int len) {
int minDiff = results[0];
for(int i = 1; i < len; i++) {
if(results[i] < minDiff) {
minDiff = results[i];
}
}
return minDiff;
}
int main() {
int numbers[17];
int n;
printf("请输入17个自然数：\n");
for(int i = 0; i < 17; i++) {
scanf("%d", &numbers[i]);
}
printf("请输入要分成几组：\n");
scanf("%d", &n);
if(n > 17 || n <= 0) {
printf("无效输入！\n");
return 0;
}
int group[n];
int results[1000]; // 假设最多有1000个组合
int resultIndex = 0;
generateCombinations(numbers, 17, group, 0, n, 0, results, &resultIndex);
int minDiff = findMinimumDifference(results, resultIndex);
printf("和之差最小的分组方案为：\n");
for(int i = 0; i < 17; i++) {
printf("%d ", group[i]);
if((i + 1) % (17 / n) == 0) {
printf("\n");
}
}
printf("每组的和之差为：%d\n", minDiff);
return 0;
}
请注意，以上代码是一个简化的示例，没有处理输入错误情况。在实际应用中，请务必添加适当的输入验证和错误处理机制。此外，由于这是一个组合爆破问题，所以随着n的增加，生成所有组合可能会导致性能下降。对于更大的问题，可以考虑使用更高效的算法来解决。
【相关推荐】
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7766887
- 这篇博客也不错, 你可以看下C 输入N个数字 判断 有几个偶数 几个奇数 并分别求和
- 除此之外, 这篇博客: C语言编程实现判断一个数是否为质数中的 例16：C语言实现输入一个大于3的整数n，判断他是否为素数（质数）。 部分也许能够解决你的问题。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^
如果以上回答对您有所帮助，点击一下采纳该答案～谢谢
代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct group {
int size;
int sum;
int *data;
} group;
int compare(const void *a, const void *b) {
group *ga = (group *)a;
group *gb = (group *)b;
return ga->sum - gb->sum;
}
void assign(int num, group *groups, int n) {
int min = 0;
for (int i = 1; i < n; i++) {
if (groups[i].sum < groups[min].sum) {
min = i;
}
}
groups[min].size++;
groups[min].sum += num;
groups[min].data = (int *)realloc(groups[min].data, groups[min].size * sizeof(int));
groups[min].data[groups[min].size - 1] = num;
}
void output(group *groups, int n) {
for (int i = 0; i < n; i++) {
printf("第%d组:", i + 1);
for (int j = 0; j < groups[i].size; j++) {
printf("%d ", groups[i].data[j]);
}
printf("\n");
}
}
void free_memory(group *groups, int n) {
for (int i = 0; i < n; i++) {
free(groups[i].data);
}
free(groups);
}
int main() {
int nums[17];
int n;
group *groups;
printf("请输入17个自然数:\n");
for (int i = 0; i < 17; i++) {
scanf("%d", &nums[i]);
}
printf("请输入要分成的组数:\n");
scanf("%d", &n);
groups = (group *)malloc(n * sizeof(group));
for (int i = 0; i < n; i++) {
groups[i].size = 0;
groups[i].sum = 0;
groups[i].data = NULL;
}
qsort(nums, 17, sizeof(int), compare);
for (int i = 0; i < 17; i++) {
assign(nums[i], groups, n);
}
qsort(groups, n, sizeof(group), compare);
printf("分好的组如下:\n");
output(groups, n);
free_memory(groups, n);
return 0;
}
直接暴力
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于排序
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int numbers[17];
int n, sum = 0;
printf("请输入17个自然数：\n");
for (int i = 0; i < 17; ++i) {
scanf("%d", &numbers[i]);
sum += numbers[i];
}
printf("请输入分成多少组：\n");
scanf("%d", &n);
int targetSum = sum / n;
// 排序输入数组
qsort(numbers, 17, sizeof(int), compare);
int groups[n][17]; // 存储每组的数
int sums[n]; // 存储每组的和
for (int i = 0; i < n; ++i) {
sums[i] = 0;
}
int currentGroup = 0;
for (int i = 16; i >= 0; --i) {
groups[currentGroup][sums[currentGroup]] = numbers[i];
sums[currentGroup] += numbers[i];
currentGroup = (currentGroup + 1) % n; // 轮流分配给每组
}
printf("分好的组为：\n");
for (int i = 0; i < n; ++i) {
printf("组 %d：", i + 1);
for (int j = 0; j < sums[i]; ++j) {
printf(" %d", groups[i][j]);
}
printf("\n");
}
return 0;
}
参考GPT：
以下是一个用C语言实现的程序，它根据用户输入的17个自然数和分组数量n，将这17个数分成n组，使得每组数的和尽可能接近。
c
#include <stdio.h>
#include <stdlib.h>
#define NUM_COUNT 17
#define GROUP_COUNT 0
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int nums[NUM_COUNT];
int groups[NUM_COUNT / GROUP_COUNT];
int group_sums[GROUP_COUNT];
int i, j, k;
int min_diff = 10000000;
printf("请输入%d个自然数：\n", NUM_COUNT);
for (i = 0; i < NUM_COUNT; i++) {
scanf("%d", &nums[i]);
}
printf("请输入分组数量n：\n");
scanf("%d", &GROUP_COUNT);
// 将数组nums排序
qsort(nums, NUM_COUNT, sizeof(int), compare);
// 将nums分成GROUP_COUNT组，每组的和最接近
for (i = 0; i < GROUP_COUNT; i++) {
groups[i] = 0;
group_sums[i] = 0;
for (j = 0; j < NUM_COUNT; j++) {
if (i == 0 && j == 0) {
groups[i] = nums[j];
group_sums[i] = nums[j];
continue;
}
if (j == 0) {
groups[i] = groups[i - 1] + nums[j];
group_sums[i] = group_sums[i - 1] + nums[j];
continue;
}
if (abs(groups[i - 1] - (groups[i - 1] + nums[j])) < min_diff) {
groups[i] = groups[i - 1] + nums[j];
group_sums[i] = group_sums[i - 1] + nums[j];
} else if (abs(group_sums[i - 1] - ((group_sums[i - 1] + nums[j]) / GROUP_COUNT)) < min_diff) {
groups[i] = groups[i] + nums[j];
group_sums[i] = group_sums[i] + nums[j];
} else {
min_diff = abs(groups[i - 1] - (groups[i - 1] + nums[j]));
for (k = i; k < GROUP_COUNT; k++) {
groups[k] = nums[j];
group_sums[k] = group_sums[k - 1] + nums[j];
}
break;
}
}
}
// 输出分组结果
printf("分组结果：\n");
for (i = 0; i < GROUP_COUNT; i++) {
printf("第%d组：%d，和为%d\n", i + 1, groups[i], group_sums[i]);
}
return 0;
}
C编程：17个自然数分为n组每组数的和之差最小得方法
1 计算所有数的和
2 定义全局变量 保存最小值，初始化为所有数的和
3 递归执行加。
这步是关键，需要定义一个额外的数组，标记是否加过了，
每次递归的时候，找一个没加过的，累加上
然后用加出的和*2-所有数的和，找到该值绝对值最小的情况，就是要求的情况了。
PS:当递归得到的差值超过已有的最小值时，可以中断查找，减少查找次数。
原理：
如果所有和为sum 而选出数的和为sum1
那么 要求的结果是|sum1-(sum-sum1)| = |2*sum1-sum|
通过这样的转换，可以减少一点运算量。
引用gpt作答：
下面是一个 C 语言的示例程序，用于将 17 个自然数分为 n 组，使得每组数的和相近。程序基于贪心算法，通过逐个分配数值到每个组中以获得最小的和之差。
#include <stdio.h>
#include <stdlib.h>
void groupNumbers(int numbers[], int n, int groups[])
{
int i, j;
int sum = 0;
int avg, remainder;
// 计算总和
for (i = 0; i < 17; i++) {
sum += numbers[i];
}
// 计算平均值和余数
avg = sum / n;
remainder = sum % n;
// 初始化每组的和
for (i = 0; i < n; i++) {
groups[i] = 0;
}
// 贪心地将数值分配到每个组中
for (i = 0; i < 17; i++) {
int minIndex = 0;
int minDiff = abs(avg - groups[0]);
// 找到和最接近平均值的组
for (j = 1; j < n; j++) {
int diff = abs(avg - groups[j]);
if (diff < minDiff) {
minIndex = j;
minDiff = diff;
}
}
// 将数值添加到最接近的组中
groups[minIndex] += numbers[i];
}
}
int main()
{
int i, n;
int numbers[17];
int groups[10]; // 假设最多分为 10 组
printf("请输入 17 个自然数：\n");
for (i = 0; i < 17; i++) {
scanf("%d", &numbers[i]);
}
printf("请输入要分为几组：\n");
scanf("%d", &n);
// 调用函数进行分组
groupNumbers(numbers, n, groups);
// 输出分组结果
for (i = 0; i < n; i++) {
printf("第 %d 组: %d\n", i + 1, groups[i]);
}
return 0;
}
你可以按照程序中的提示，依次输入 17 个自然数和要分为的组数，然后程序会输出每组的和。请注意，由于具体示例图片未提供，所以此程序中的输出方式是按照组的序号和和值进行输出。
可以参考代码：
#include <stdio.h>
#define NUM_COUNT 17
#define GROUP_COUNT 3
int main() {
int numbers[NUM_COUNT];
int totalSum = 0;
int groupSum[GROUP_COUNT] = {0};
int groupIndex = 0;
int max = 0;
int min = 1000000;
int userInput;
int i;
printf("请输入%d个自然数：\n", NUM_COUNT);
for (i = 0; i < NUM_COUNT; i++) {
scanf("%d", &userInput);
numbers[i] = userInput;
totalSum += userInput;
if (userInput > max) {
max = userInput;
}
if (userInput < min) {
min = userInput;
}
}
printf("请输入%d组：\n", GROUP_COUNT);
for (i = 0; i < GROUP_COUNT; i++) {
printf("组%d：\n", i+1);
groupSum[i] = totalSum / GROUP_COUNT;
groupIndex = 0;
totalSum = 0;
max = 0;
min = 1000000;
while (groupIndex < NUM_COUNT) {
int j;
int currentIndex = -1;
int currentDifference = 1000000;
for (j = 0; j < NUM_COUNT; j++) {
if (numbers[j] != groupSum[i]) {
if ((numbers[j] - groupSum[i]) < currentDifference) {
currentDifference = numbers[j] - groupSum[i];
currentIndex = j;
}
} else {
groupIndex++;
}
}
printf("%d ", numbers[currentIndex]);
groupSum[i] += numbers[currentIndex];
totalSum += numbers[currentIndex];
if (numbers[currentIndex] > max) {
max = numbers[currentIndex];
}
if (numbers[currentIndex] < min) {
min = numbers[currentIndex];
}
numbers[currentIndex] = 0;
}
}
printf("\n");
return 0;
}
参考gpt
#include <stdio.h>
#include <stdlib.h>
// 计算数组元素之和
int sum(int arr[], int n) {
int s = 0;
for (int i = 0; i < n; i++) {
s += arr[i];
}
return s;
}
// 递归函数，将数组分为n组，返回每组的和之差最小值
int minDiff(int arr[], int n, int groups, int groupSum[], int minDiffValue, int result[]) {
// 所有数都已分组，计算和之差的绝对值
if (n == 0) {
int diff = abs(groupSum[0] - groupSum[1]);
if (diff < minDiffValue) {
minDiffValue = diff;
// 将结果保存到result数组中
for (int i = 0; i < groups; i++) {
result[i] = groupSum[i];
}
}
return minDiffValue;
}
// 将当前数分配给每个组，递归调用
for (int i = 0; i < groups; i++) {
groupSum[i] += arr[n - 1];
int diff = minDiff(arr, n - 1, groups, groupSum, minDiffValue, result);
if (diff < minDiffValue) {
minDiffValue = diff;
}
groupSum[i] -= arr[n - 1];
}
return minDiffValue;
}
int main() {
int arr[17];
int n;
printf("请输入17个自然数：\n");
for (int i = 0; i < 17; i++) {
scanf("%d", &arr[i]);
}
printf("请输入要分成的组数：\n");
scanf("%d", &n);
int groupSum[n]; // 每组的和
int result[n]; // 分组结果
// 初始化groupSum数组和result数组
for (int i = 0; i < n; i++) {
groupSum[i] = 0;
result[i] = 0;
}
int minDiffValue = minDiff(arr, 17, n, groupSum, sum(arr, 17), result);
printf("分组结果为：\n");
for (int i = 0; i < n; i++) {
printf("第%d组：", i + 1);
for (int j = 0; j < 17; j++) {
if (result[j] == i) {
printf("%d ", arr[j]);
}
}
printf("\n");
}
printf("每组的和之差最小值为：%d\n", minDiffValue);
return 0;
}
在程序中，首先要求用户输入17个自然数和要分成的组数n。然后，使用递归函数minDiff来计算分组结果和每组的和之差最小值。最后，将分组结果和最小值输出。
请注意，此程序假设用户输入的17个自然数是有效的，并且输入的组数n不超过17。如果输入无效或超出范围，程序可能会出现错误。建议在实际使用时添加适当的输入验证和错误处理逻辑。
#include <stdio.h>
#include <stdlib.h>
void findMinDiff(int arr[], int n, int m) {
if (m > n) {
printf("无法将数组分为更多的组！");
return;
}
if (n % m != 0) {
printf("无法将数组均匀分为指定的组数！");
return;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
int targetSum = sum / m;
int currSum = 0;
int groupCount = 1;
for (int i = 0; i < n; i++) {
currSum += arr[i];
if (currSum > targetSum) {
printf("\n");
currSum = arr[i];
groupCount++;
}
printf("%d ", arr[i]);
}
if (groupCount < m) {
printf("\n无法将数组分为指定的组数！");
}
}
int main() {
int arr[17];
int n, m;
printf("请输入17个自然数：\n");
for (int i = 0; i < 17; i++) {
scanf("%d", &arr[i]);
}
printf("请输入要分成的组数：\n");
scanf("%d", &m);
n = sizeof(arr) / sizeof(arr[0]);
printf("分组结果如下：\n");
findMinDiff(arr, n, m);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int minDiff = 999999; // 初始化最小差值为一个较大的数
int targetSum; // 目标和
int groupSum[17]; // 每个组的和
int group[17]; // 每个数所属的组
int input[17]; // 用户输入的数
int n; // 组数
// 计算每个组的和
void calculateGroupSum(int index) {
int i, j;
for (i = 0; i < n; i++) {
groupSum[i] = 0; // 初始化每个组的和为0
}
for (i = 0; i < 17; i++) {
groupSum[group[i]] += input[i]; // 将每个数加到对应的组中
}
}
// 递归函数，用于将每个数分配到组中
void assignGroup(int index) {
if (index == 17) {
calculateGroupSum(0); // 计算每个组的和
int maxSum = groupSum[0]; // 最大和
int minSum = groupSum[0]; // 最小和
for (int i = 1; i < n; i++) {
if (groupSum[i] > maxSum) {
maxSum = groupSum[i];
}
if (groupSum[i] < minSum) {
minSum = groupSum[i];
}
}
int diff = maxSum - minSum; // 计算组与组和的差值
if (diff < minDiff) {
minDiff = diff; // 更新最小差值
}
return;
}
for (int i = 0; i < n; i++) {
group[index] = i; // 将第index个数分配到第i组
assignGroup(index + 1); // 递归调用分配下一个数
}
}
int main() {
printf("请输入17个自然数：\n");
for (int i = 0; i < 17; i++) {
scanf("%d", &input[i]); // 输入17个自然数
}
printf("请输入分组数n：\n");
scanf("%d", &n); // 输入分组数
assignGroup(0); // 开始分组
printf("组与组和的差最小值为：%d\n", minDiff); // 输出最小差值
return 0;
}
从小到大排序，依次分配就行了