欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

杭电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