最長公共子串
題目描述
給定兩個字串 a、b，現有k次機會對字串中的字符進行修改，使修改后兩個字串的最長公共子串最長，
每一次修改，可以選擇a、b字串中某一個串的任意位置修改成任意字符，輸入格式:
第一行包括一個正整數 k，
第二行和第三行分別輸入字串 a、b，（每個串的長度不超過500）輸出格式:
輸出為一個整數，表示修改后的兩個串的最長公共子串長度，
解題思路
采用二重回圈，在 a、b 字串中選定不同起始位置，列舉所有可能，找最長子串的長度，
完整代碼
#include<stdio.h>
#include<string.h>
int main()
{
int k, n1, n2, ans = 0, count, i, j, p, q;
char a[505], b[505];
scanf("%d", &k);
getchar();
gets(a);
gets(b);
n1 = strlen(a);
n2 = strlen(b);
for (i = 0; i < n1; i++) {
for (j = 0; j < n2; j++) {
p = i;
q = j;
count = 0;
while (count != k && p != n1 && q != n2) {
if (a[p] != b[q]) {
count++;
}
p++;
q++;
}
if (p - i > ans) {
ans = p - i;
}
}
}
printf("%d", ans);
return 0;
}
旋轉骰子
題目描述
瑪莎有 n 個骰子，每個骰子的 6 個面上都恰好有一個 0 到 9 之間的數字，
現在瑪莎將利用這 n 個骰子來制作新數字，她把 n 個骰子擺成一排，然后從左到右查看骰子的上表面并讀取，即可得到一個新數字，隨后她不斷的旋轉每個骰子的面就可以得到不同的新數字，旋轉骰子需要滿足以下規則：
- 制作的數字不能包含前導零；
- 制作新數字時不需要使用所有的骰子；
- 使用骰子旋轉，無法將數字 9 轉換為數字 6 ，反之亦然，
給定 n 個骰子，瑪莎可以用它們構成從 1 到 x 的所有整數，瑪莎想知道，對于給定的 n 個骰子，這個 x 的最大取值是多少呢？
輸入格式:
第一行僅一個整數 n ，表示骰子的數量（1≤n≤3），
接下來 n 行，每行包含6個整數 a[i][j]（0≤ a[i][j] ≤9），表示第 i 個骰子的第 j 個面上的數字，輸出格式:
輸出一個整數，即最大數 x ，瑪莎可以使用她的骰子構成數字從 1 到 x，如果無法構成 1，則輸出0，
解題思路
1.最多 3 個骰子的條件下，x 的最大值為 98，
2.任意一個骰子組成個位數，任意兩個骰子組成十位數，1-100 分別對應 visit[1]-visit[100]，若組成數字 i，則 visit[i]=1，四重回圈列舉任意兩個骰子構成的十位數，
3.找出最大 x，
完整代碼
#include<stdio.h>
int main()
{
int n, i, j, p, q;
int a[3][6], visit[100] = { 0 };
scanf("%d", &n);
for (i = 0; i < n; i++) {
for (j = 0; j < 6; j++) {
scanf("%d", &a[i][j]);
visit[a[i][j]] = 1;
}
}
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
for (p = 0; p < 6; p++) {
for (q = 0; q < 6; q++) {
visit[a[i][p] * 10 + a[j][q]] = 1;
visit[a[j][q] * 10 + a[i][p]] = 1;
}
}
}
}
for (i = 1; i < 100; i++) {
if (visit[i] == 0) {
break;
}
}
printf("%d", i - 1);
return 0;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/47166.html
標籤：C
上一篇：C語言學習(2)
下一篇：列印指定年份的日歷