An interesting question.

diao_david (David Diao)
本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛
This is a prelimitary question about Embeded Code Programmer. I failed in that interview, but I really think this question is very interesting.
Which expert can tell me what's wrong wtih my answers.

Consider a computer with standard CPU architecture running at 50MHz, one megabyte of memory, no external storage and no external input.

a) Give an approximate upper bound on the running time of the longest-running possible (terminating!) program.

b) Write a small (less than 10 lines) terminating C program with a running time of more than a googol (10^100) years. Assume a 32-bit word size and no external inputs.

You may disregard practical limitations, like energy resources or the end of the universe.

Answer:
a) Depending on the average length of instructions and average time cycles used by these instructions, the answer is between 0.01-0.08s.
b)
#include <mem.h>
#include <stdlib.h>
void main ()
{
int *vals,*ptr;
vals = malloc(sizeof(int)*200);
memset (vals,'\0',sizeof(int)*201);
while(!vals[200])
{
*(ptr = vals) += 1;
while (*ptr == 10)
{
*ptr++ = 0;
*ptr += 1;
}
}
free(vals);
}
更多精彩文章及讨论,请光临枫下论坛. 网址: rolia.net/zh
(#25443@0)
2001-2-9 -05:00

回到话题: An interesting question.

回到论坛: HOME枫下论坛枫下论坛主坛工作学习IT技术讨论

URL:   
http://www.rolia.net/zh/post.php?f=0&p=25443