題目描述

? 小李的電腦上安裝了一個機器翻譯軟件，他經(jīng)常用這個軟件來翻譯英語文章。
?這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，
如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然后翻譯，
并將這個單詞和譯義放入內存，以備后續(xù)的查找和翻譯。? 假設內存中有 M 個單元，每單元能存放一個單詞和譯義。
每當軟件將一個新單詞存入內存前，如果當前內存中已存入的單詞數(shù)不超過 M?1，軟件會將新單詞存入一個未使用的內存單元；
若內存中已存入 M 個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。
?假設一篇英語文章的長度為 N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？
假設在翻譯開始前，內存中沒有任何單詞。

輸入

? 共 2 行。每行中兩個數(shù)之間用一個空格隔開。

? 第一行為兩個正整數(shù) M,N，代表內存容量和文章的長度。

? 第二行為 N 個非負整數(shù)，按照文章的順序，每個數(shù)（大小不超過 1000）代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數(shù)相同。

輸出

? 一個整數(shù)，為軟件需要查詞典的次數(shù)。

樣例輸入

3 7
1 2 1 5 4 4 1

樣例輸出

5

樣例說明

整個查字典過程如下：每行表示一個單詞的翻譯，冒號前為本次翻譯后的內存狀況：

空：內存初始狀態(tài)為空。

1．1：查找單詞1并調入內存。

2． 12：查找單詞2并調入內存。

3． 12：在內存中找到單詞1。

4． 125：查找單詞5并調入內存。

5． 254：查找單詞4并調入內存替代單詞1。

6． 254：在內存中找到單詞4。

7． 541：查找單詞1并調入內存替代單詞2。

共計查了5次詞典。

數(shù)據(jù)規(guī)模與約定

? > 時間限制：1 s

? > 內存限制：256 M

? > 100% 的數(shù)據(jù)保證 0≤M≤100，0≤N≤1000

代碼

#include <stdio.h>
#include <stdlib.h>

int chapter[1005] = {0};
void add_word(int *memory, int word, int m) {
  for (int i = 0; i < m; i++) {
    if (memory[i] == -1) {
      memory[i] = word;
      break ;
    }
  }
}

void replace_first_word(int *memory, int word, int m) {
  for (int i = 0; i < m - 1; i++) {
    memory[i] = memory[i + 1];
  }
  memory[m - 1] = word;
}

int is_found(int *memory, int word, int m) {
  for (int i = 0; i < m; i++) {
    if (memory[i] == word) {
      return 1;
    }
  }
  return 0;
}

void find_count(int *chapter, int m, int n) {
  int count = 0, size = 0, memory[105] = {0};
  
  for (int i = 0; i  < m; i++) {
    memory[i] = -1;
  }

  for (int i = 0; i < n; i++) {
    if (!is_found(memory, chapter[i], m)) {
      if (count < m) {
        add_word(memory, chapter[i], m);
      } else {
        replace_first_word(memory, chapter[i], m);
      }
      count++;
    }
  }

  printf("%d", count);
}

int main() {
  int m, n;
  scanf("%d%d\n", &m, &n);

  for (int i = 0; i < n; i++) {
    scanf("%d", &chapter[i]);
  }
  find_count(chapter, m, n);
  return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-510886.html

到了這里，關于OJ# 376 機器翻譯的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！