用c语言完成:1. 有数组 B[M](无重复元素) 1.1:输出从中取 k 个元素的组合 1.2:输出从中取 k 个元素的排列 1.3: 给定一个W和N,从B中找出k个元素,使这k个元素 之和小于等于 W 且 k 小于等于 N;输出结果中与 W 最接近 的那个 2. 给定一个矩阵 a[M][N],类似 1111011 0001000 0011010 1010011 1111100 输出所有为 0 的区域面积。如图有 4 个区域都为 0,面积分 别为 6 6 2 2
时间: 2023-05-31 16:02:23 浏览: 83
1.1.组合算法:
#include <stdio.h>
#define M 5
void combination(int B[], int n, int k, int start, int result[], int count)
{
if (count == k) {
for (int i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return;
}
for (int i = start; i <= n - (k - count); i++) {
result[count] = B[i];
combination(B, n, k, i + 1, result, count + 1);
}
}
int main()
{
int B[M] = {1, 2, 3, 4, 5};
int k = 3;
int result[k];
combination(B, M, k, 0, result, 0);
return 0;
}
1.2.排列算法:
#include <stdio.h>
#define M 5
void permutation(int B[], int n, int k, int used[], int result[], int count)
{
if (count == k) {
for (int i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return;
}
for (int i = 0; i < n; i++) {
if (used[i] == 0) {
result[count] = B[i];
used[i] = 1;
permutation(B, n, k, used, result, count + 1);
used[i] = 0;
}
}
}
int main()
{
int B[M] = {1, 2, 3, 4, 5};
int k = 3;
int used[M] = {0};
int result[k];
permutation(B, M, k, used, result, 0);
return 0;
}
1.3.背包问题算法:
#include <stdio.h>
#define M 5
void subset_sum(int B[], int n, int k, int W, int result[], int count, int sum, int *min_diff, int *min_sum)
{
if (count == k) {
if (sum <= W && W - sum < *min_diff) {
*min_diff = W - sum;
*min_sum = sum;
}
return;
}
for (int i = 0; i < n; i++) {
result[count] = B[i];
subset_sum(B + i + 1, n - i - 1, k, W, result, count + 1, sum + B[i], min_diff, min_sum);
}
}
int main()
{
int B[M] = {1, 2, 3, 4, 5};
int k = 3;
int W = 10;
int result[k];
int min_diff = W;
int min_sum = 0;
subset_sum(B, M, k, W, result, 0, 0, &min_diff, &min_sum);
printf("最接近%d的和为%d\n", W, min_sum);
return 0;
}
2.矩阵面积算法:
#include <stdio.h>
#define M 5
#define N 7
void dfs(int a[M][N], int x, int y, int *area)
{
if (x < 0 || x >= M || y < 0 || y >= N || a[x][y] != 0) {
return;
}
(*area)++;
a[x][y] = -1;
dfs(a, x + 1, y, area);
dfs(a, x - 1, y, area);
dfs(a, x, y + 1, area);
dfs(a, x, y - 1, area);
}
int main()
{
int a[M][N] = {{1, 1, 1, 1, 0, 1, 1},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 1, 1, 0, 1, 0},
{1, 0, 1, 0, 0, 1, 1},
{1, 1, 1, 1, 1, 0, 0}};
int area = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (a[i][j] == 0) {
dfs(a, i, j, &area);
printf("面积为%d\n", area);
area = 0;
}
}
}
return 0;
}
阅读全文