杭电oj1708(Fibonacci String)
程序员文章站
2022-04-01 17:21:18
...
杭电oj1708(Fibonacci String)
题目描述
对字符串进行Fibonacci运算,输出第K项所含各个字母的数目
Sample Input
1
ab bc 3
Sample Output
a:1
b:3
c:2
d:0
e:0
f:0
g:0
h:0
i:0
j:0
k:0
l:0
m:0
n:0
o:0
p:0
q:0
r:0
s:0
t:0
u:0
v:0
w:0
x:0
y:0
z:0
答案
水题~
只要对所含字母数进行Fibonacci运算就可以了
注意如果用函数的递归调用会超时
AC代码:
#include <string.h>
#include <ctype.h>
#include <iostream>
using namespace std;
void count_letter(char *, int *);
void copy_total(int *, int *);
void add_total(int *, int *, int *);
void fibonacci(int *, int *, int *, int);
int main() {
int N, K;
char str_0[50], str_1[50];
int total_0[50], total_1[50], total_ans[50];
cin >> N;
while (N--) {
/*Input* and initialize*/
cin >> str_0 >> str_1 >> K;
for (int i = 0; i < 26; i++)
total_0[i] = total_1[i] = total_ans[i] = 0;
/*Count the letter*/
count_letter(str_0, total_0);
count_letter(str_1, total_1);
/*Calculate*/
fibonacci(total_0, total_1, total_ans, K);
/*Output*/
for (int i = 0; i < 26; i++)
printf("%c:%d\n", i + 'a', total_ans[i]);
printf("\n");
}
}
void count_letter(char *str, int *total_ans) {
for (int i = 0; str[i] != '\0'; i++)
total_ans[str[i] - 'a']++;
}
void copy_total(int *total_dest, int *total_src) {
for (int i = 0; i < 26; i++)
total_dest[i] = total_src[i];
}
void add_total(int *total_1, int *total_2, int *total_ans) {
for (int i = 0; i < 26; i++)
total_ans[i] = total_1[i] + total_2[i];
}
void fibonacci(int *total_0, int *total_1, int *total_ans, int k) {
if (k == 0) {
copy_total(total_ans, total_0);
return;
}
else if (k == 1) {
copy_total(total_ans, total_1);
return;
}
else {
int total_k_2[50], total_k_1[50], total_k[50];
copy_total(total_k_2, total_0);
copy_total(total_k_1, total_1);
for (int i = 2; i <= k; i++) {
add_total(total_k_2, total_k_1, total_k);
copy_total(total_k_2, total_k_1);
copy_total(total_k_1, total_k);
}
copy_total(total_ans, total_k);
}
}
上一篇: 北邮oj--矩阵幂