经典算法题

只看该作者 · 2012-4-10 21:50

代码如下：
int A[100][150],B[150][200],C[100][200];

int i,j,k;

for(i=1;i<=100;i++)

for(j=1;j<=200;j++)

for(k=1;k<150;k++)

C[i,j]=C[i,j]+A[i,k]*B[k,j];

假设矩阵A，B的初始值已置好，矩阵C初始为0，各矩阵均以页为单位连续存放，又假定一个整数占用一个字（2字节），代码以及变量i,j,k放在其它页面里，并且存取变量i,j,k时不缺页。主存初始为空，在请求分页存储管理中，页面淘汰算法为FIFO。

问：作业分配10各页面，每个页面为100各字，给矩阵A，B，C使用。问执行上面的程序时，缺页次数是多少？当程序执行完时，留在内存的10各页面各属于哪些矩阵？
我以以下程序进行验证，得出的结果总是错的：

typedef struct
{
int data;
void
*prev;
void
*next;
}NODE;

bool visitPage(int page, NODE *p);
bool fifoAdjustPage(int page, NODE **head);
void printPage(NODE* head, int state);

typedef struct
{
void (*dummy)(void
*);
const
char
*szName;
const
char
*
const
*aszPredecessors;
const
char
*
const
*aszSuccessors;
int nOrder;
} TSortData;

//全局变量
int printNum =
1000; //打印多少个
int lackPageNum =
0; //总共缺页数
NODE data[10]; //实际数据

int _tmain(int argc, _TCHAR* argv[])
{
testFifo();

return
0;
}

void testFifo()
{
int i, j, k, page, state;
NODE *head, *p;
bool isAdjust; //是否调整过页面

//初始化

for(i=0; i<10; i++)
{
      if (0
== i)
      {
         data.prev =
&(data[9]);
         data.next =
&(data[i+1]);
      }else
if(9
== i)
      {
         data.prev =
&(data[i-1]);
         data.next =
&(data[0]);;
      }else
      {
         data.prev =
&(data[i-1]);
         data.next =
&(data[i+1]);
      }
      data.data =
0;

}

head =
&(data[0]);

/*
A[100][150], B[150][200], C[100][200]

C[i,j]=C[i,j]+A[i,k]*B[k,j];
假定A占用的页面为1-150, B为151-450, C为451-650
第个整型假如占1个字，现在只有10个页面可分配，一个页面为100字
*/
for(i=0; i<100; i++)
      for(j=0; j<200; j++)
         for(k=0; k<150; k++)
         {
            state =
0;
            p = NULL;

            //访问A
            page = (i*150
+ k)/100
+
1;
            if (visitPage(page, head))
            {
            }else
            {
                  lackPageNum++;
                  state |=1;
                  isAdjust = fifoAdjustPage(page, &head);
            }
            //再访问B
            page = (k*200
+ j)/100
+
1
+
150;
            if (visitPage(page, head))
            {
            }else
            {
                  lackPageNum++;
                  state |=2;
                  isAdjust = fifoAdjustPage(page, &head);
            }

            //再访问C
            page = (i*200
+ j) /
100
+
1
+
450;
            if (visitPage(page, head))
            {
            }else
            {
                  lackPageNum++;
                  state |=4;
                  isAdjust = fifoAdjustPage(page, &head);
            }
            printPage(head, state);
         }

         printNum =
3000000;
         printPage(head, state);
         printf("总共缺少页面:%d\n", lackPageNum);
}

//该页是否在其中
bool visitPage(int page, NODE *head)
{
NODE *p=head;
int i=0;
while(i<10)
{
      if (p->data == page)
         return
true;
      p = (NODE*)(p->next);
      i++;
}
return
false;
}

//输出页面
void printPage(NODE *head, int state)
{
int i=0;
static
int j=0;

if (printNum >
0)
{
      //NODE *p = (NODE*)(head->prev);
      NODE *p = head;
      j++;
      printf("%d:", j);
      while(i<10)
      {
         printf(" %d", p->data);
         p = (NODE*)(p->next);
         i++;
      }

      printNum--;
      i=0;
      if ((state&1) >
0) i++;
      if ((state&2) >
0) i++;
      if ((state&4) >
0) i++;
      printf(" 缺页次数:%d", i);
      printf("\n");
}
}

//fifo调入页面
bool fifoAdjustPage(int page, NODE **head)
{
NODE *p, *p1;
int i=0;

p =
*head;

//有空的，不调整头

while(i <
10)
{
      if (0
== p->data)
      {
         p->data = page;
         return
false;
      }
      p = (NODE*)(p->next);
      i++;
}

//最后一个放到前面来
p =
*head;
p->data = page;
//((NODE*)(p->prev))->next = p;

//调整头
p1 = (NODE *)(p->next);
*head = p1;
return
true;
}

只看该作者 · 2012-4-10 22:08

LZ很有思想

只看该作者 · 2012-4-10 22:38

GOOD

只看该作者 · 2012-4-11 18:48

没看太明白

只看该作者 · 2012-4-11 22:19

这个算法经典在哪里？

经典算法题

相关下载

相关帖子