|
页面调度算法
在计算机中，页式虚拟存储器实现的一个难点是设计页面调度（置换）算法。其中一种实现方式是FIFO算法。
FIFO算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。
假设Cache的大小为2,有5个页面请求，分别为 2 1 2 3 1，则Cache的状态转换为：(2)->(2,1)->(2,1)->(1,3)->(1,3)，其中第1,2,4次缺页，总缺页次数为3。
现在给出Cache的大小n和m个页面请求，请算出缺页数。
输入描述:
输入包含多组测试数据。
对于每组测试数据，第一行是整数n，第二行是整数m。
然后有m个整数，代表请求页编号。
保证：
2<=n<=20,1<=m<=100，1<=页编号<=200.
输出描述:
对于每组数据，输出一个整数，代表缺页数
输入例子:
2
5
2
1
2
3
1
输出例子:
3
// ConsoleApplication3.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <vector>
bool vecfind(std::vector<int>& vec, int num) {
int len = vec.size();
for (int i = 0; i < len; ++i){
if (num == vec[i])
return true;
}
return false;
}
int main() {
int n, m;
while (std::cin >> n >> m) {
std::vector<int> vecCache;
std::vector<int> vecPage(m);
int cnt = 0;
for (int i = 0; i < m; ++i) {
std::cin >> vecPage[i];
}
for (int i = 0; i < m; ++i) {
if (vecfind(vecCache, vecPage[i])) {
continue;
}
else {
if (vecCache.size() < n) {
vecCache.push_back(vecPage[i]);
}
else{
vecCache.erase(vecCache.begin());
vecCache.push_back(vecPage[i]);
}
++cnt;
}
}
std::cout << cnt << std::endl;
}
return 0;
}
第二次做：
// ConsoleApplication3.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <vector>
bool vecfind(std::vector<int>& vec, int num) {
int len = vec.size();
for (int i = 0; i < len; ++i){
if (num == vec[i])
return true;
}
return false;
}
int main() {
int n, m;
while (std::cin >> n >> m) {
std::vector<int> vecCache;
std::vector<int> vecPage(m);
int cnt = 0;
for (int i = 0; i < m; ++i) {
std::cin >> vecPage[i];
}
for (int i = 0; i < m; ++i) {
if (vecfind(vecCache, vecPage[i])) {
continue;
}
else {
if (vecCache.size() < n) {
vecCache.push_back(vecPage[i]);
}
else{
vecCache.erase(vecCache.begin());
vecCache.push_back(vecPage[i]);
}
++cnt;
}
}
std::cout << cnt << std::endl;
}
return 0;
}
第三次做：
#include <iostream>
#include <queue>
#include <vector>
using namespace::std ;
bool isFind( deque<int>& dq, int target ) {
for ( int i = 0; i < dq.size(); ++ i ) {
if ( dq[i] == target ) return true ;
}
return false ;
}
int main() {
int n, m ;
while ( cin >> n >> m ) {
if ( n <= 0 || m <= 0 ) continue ;
vector<int> vec( m ) ;
for ( int i = 0; i < m; ++ i ) {
cin >> vec[i] ;
}
deque<int> cache ;
int fail = 0 ;
for ( int i = 0; i < m; ++ i ) {
if ( isFind( cache, vec[i] ) == false ) {
++ fail ;
if ( cache.size() == n ) {
cache.pop_front() ;
cache.push_back( vec[i] ) ;
}
else if ( cache.size() < n ) {
cache.push_back( vec[i] ) ;
}
}
else continue ;
}
cout << fail << endl ;
}
return 0 ;
}
| 
转播
