| |
 |
|
 |
 |
| Factstone Benchmark | 2006-09-20 01:44:25 |
| 标签： |  缩起正文  字号：大 小 |
 http://192.168.100.16/showproblem.php?pid=1141
题意：
假设1960年出现了一部计算机只能容纳4-bit的数值数据。接着以每10年为一个世代，数值范围皆为前一世代的两倍，如：1970为8-bit。若给定一年份，试找出在n!中，其数值可容纳于该年份之位数范围内最大的n值。
题意范例：
输入输出
19603
19818
199912
2160254016
0
解法：
暴力法建表求解
解法范例：
(1) 题意
年份1960197019801990200020102020
位数 4 8 16 32 64 128 256
年份203020402050 …2160
位数 51210242048 222
(2) 算法
n123 4 5 6 7 8 …
n!12624120720504040320
位数123 5 7 10 13 16
符合19601970 1980
(3) 找寻位数时，使用
log2(n!)=log2(1*2*3…*n)=log2(1)+log2(2)+…+log2(n)
(4) 为避免重复计算，因此建表使用之，如果做到需要的数，就独立出来。
使用，array[n]=array[n-1]+array[n];
n12345678…
log2(n)011.3+22.3+2.5+2.7+3
位数12357101316
程序：
/* 主程序部份 */
#include <stdio.h>
int main()
{
int want;
int result[23]={3,5,8,12,20,34,57,98,170,300,536,966,1754,3210,5910,
10944,20366,38064,71421,134480,254016};
while(1)
{
scanf("%d",&want);
if(want==0) break;
printf("%d\n",(int)result[(want-1960)/10]);
}
return 0;
}
/* 建表部份 */
#include <stdio.h>
#include <math.h>
#define MAX 100000
#define Bit 50
int main()
{
int i,j,tmp,want;
double array1[MAX],result[50],buffer;
for(i=0;i<MAX;i++) array1[i]=i+1;
for(i=0;i<MAX;i++) array1[i]=log2(array1[i]);
for(i=1;i<MAX;i++) array1[i]=array1[i-1]+array1[i];
tmp=4;
j=0;
for(i=0;i<MAX;i++)
{
if(ceil(array1[i])>tmp){
result[j]=i;
j++;
tmp=tmp*2;
}
}
buffer=array1[MAX-1];
for(i=0;i<MAX;i++) array1[i]=MAX+i+1;
for(i=0;i<MAX;i++) array1[i]=log2(array1[i]);
array1[0]=buffer+array1[0];
for(i=1;i<MAX;i++) array1[i]=array1[i-1]+array1[i];
for(i=0;i<MAX;i++)
{
if(ceil(array1[i])>tmp){
result[j]=MAX+i;
j++;
tmp=tmp*2;
}
}
buffer=array1[MAX-1];
for(i=0;i<MAX;i++) array1[i]=2*MAX+i+1;
for(i=0;i<MAX;i++) array1[i]=log2(array1[i]);
array1[0]=buffer+array1[0];
for(i=1;i<MAX;i++) array1[i]=array1[i-1]+array1[i];
for(i=0;i<MAX;i++)
{
if(ceil(array1[i])>tmp){
result[j]=2*MAX+i;
j++;
tmp=tmp*2;
}
}
for(i=0;i<50;i++) printf("%d,",(int)result[i]);
getchar();
return 0;
}
|
| 回复() | 人气() | 引用() | 推荐 | 保存日志 | 问题日志 | 收藏到网摘 | 返回圈子首页 |
|
|
 |
|
 |
|
....
