机器翻译
题目背景
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
题目描述
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有MM个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M-1M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入MM个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为NN个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入输出格式
输入格式：
共22行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M,NM,N，代表内存容量和文章的长度。
第二行为NN个非负整数，按照文章的顺序，每个数（大小不超过10001000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
输出格式：
一个整数，为软件需要查词典的次数。
输入输出样例
代码
#include<stdio.h>
int searCnt(int mrt[],int ct[]);
int M,N;
int main(){
scanf("%d %d",&M,&N);
int mry[M];
int ct[N];
for(int i=0;i<N;i++){
scanf("%d",&ct[i]);
}
int nums = searCnt(mry,ct);
printf("%d\n",nums);
return 0;
}
int searCnt(int mry[],int ct[]){
int old = 0;
int curS = 0, count = 0;
mry[0] = ct[0]; old = 0;
count++; curS++;
for(int i=1;i<N;i++){
for(int j=0;j<curS;j++){
if(ct[i]==mry[j]){
break;
}else { //ct[i] != mry[j]
if(j==curS-1){
if(curS<M){
mry[curS++] = ct[i];
count++; break;
}
mry[old] = ct[i];
old = (old+1)%M;
count++; break;
}
continue;
}
}
}
return count;
}
代码思想
解法一：
来自我一位朋友，他用的队列思想。他将内存看做成一个队列，start指向对头，end指向队尾。时间复杂度为O（N*curS），其中curS为当前存入的数字个数，curS从0到M（M为内存空间）。空间复杂度方面：创建一个1000容量的数组。
解法二：
我自己局限的想法（上述代码），不过我改过后，时间复杂度同为O（N*curS），空间复杂度为O（M+N），N为给定序列长度。
这题的思想其实很简单，就是判定给定的序列的每一位数字是否在“内存”中已经存在，若已然存在，则不需要去访问“字典”（虚拟化的，并不存在），否则你将要访问字典。我们需要做的就是在“内存”中未找到匹配的数字时，使访问“字典”的次数count++即可！
京公网安备 11010502036488号