第一题
由1,3,4,5,7,8这6个数字组成六位数中,能被11整除的最大的数是多少。
解答
可以使用暴力枚举法,将1,3,4,5,7,8的所有排列组合情况求出来,判断它们是否能被11整除,然后取其中能被11整除的最大值。但是这个方法的时间复杂度很高,不适合实际应用。
另一种更高效的方法是利用11的特殊性质:一个整数能被11整除,当且仅当它各位数字之和的交替求和的结果为11的倍数。例如,121是11的倍数,因为1-2+1=0,0是11的倍数。
根据这个特性,可以求出所有由1,3,4,5,7,8组成的数的各位数字之和的交替求和的结果,判断是否为11的倍数,然后取其中能被11整除的最大值。
#include <stdio.h>
int main() {
int digits[] = {1, 3, 4, 5, 7, 8};
int num_digits = 6;
int max_num = -1;
for (int i = 0; i < num_digits; i++) {
for (int j = 0; j < num_digits; j++) {
if (j == i) continue;
for (int k = 0; k < num_digits; k++) {
if (k == i || k == j) continue;
for (int l = 0; l < num_digits; l++) {
if (l == i || l == j || l == k) continue;
for (int m = 0; m < num_digits; m++) {
if (m == i || m == j || m == k || m == l) continue;
for (int n = 0; n < num_digits; n++) {
if (n == i || n == j || n == k || n == l || n == m) continue;
int sum = digits[i] - digits[j] + digits[k] - digits[l] + digits[m] - digits[n];
if (sum % 11 == 0) {
int num = digits[i] * 100000 + digits[j] * 10000 + digits[k] * 1000 + digits[l] * 100 + digits[m] * 10 + digits[n];
if (num > max_num) {
max_num = num;
}
}
}
}
}
}
}
}
printf("The largest number composed of 1,3,4,5,7,8 that is divisible by 11 is: %d\n", max_num);
return 0;
}
上一题的升级版
时间复杂度很高
将指定六个数改成任意6个数
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
void permute(char *str, int l, int r, int *max_num) {
if (l == r) {
int num = atoi(str);
if (num % 11 == 0 && num > *max_num) {
*max_num = num;
}
} else {
for (int i = l; i <= r; i++) {
swap((str + l), (str + i));
permute(str, l+1, r, max_num);
swap((str + l), (str + i));
}
}
}
int main() {
char str[7];
int max_num = -1;
scanf("%s", str);
permute(str, 0, strlen(str)-1, &max_num);
printf("%d\n", max_num);
return 0;
}