Posted on 2011-09-25 23:45
Uriel 阅读(415)
评论(2) 编辑 收藏 引用 所属分类:
考研&保研复试上机题
这套题纠结了一晚上。。
1. 质因数的个数
这个还比较水。。
//2007年清华大学计算机研究生机试题 质因数的个数
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() 
{
int n, i, cnt;
while(~scanf("%d", &n)) {
i = 2; cnt = 1;
while(i <= sqrt(n)) {
if(n % i == 0) {
n /= i;
cnt++;
}
else
++i;
}
printf("%d\n", cnt);
}
return 0;
}2. 10进制 VS 2进制
这题木有什么好想法。。发现网上一位大牛
http://blog.csdn.net/herechaos/article/details/5397430也是直接做的。。就直接模拟之了。。结果就是跑得暴慢。。路过的大牛有什么好想法的不吝赐教啊。。
PS: 方法见上面链接的大牛Blog，不过网上这位大牛的源码AC不能，有几处小bug。。
//2007年清华大学计算机研究生机试题 10进制 VS 2进制
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int b[8010], c[80100], la, lb, lc;
char a[8010];
void pw(int x) {
int i, j, k;
memset(c, 0, sizeof(c));
c[0] = 1;
lc = 1;
for(i = 0; i < x; ++i) {
for(j = 0; j < lc; ++j) c[j] *= 2;
for(k = 0; k < lc || c[k]; ++k) {
c[k + 1] += (c[k] / 10);
c[k] %= 10;
}
lc = k;
}
la = (lc > la ? lc : la) + 1;
for(i = 0; i < la; ++i) {
a[i] += c[i];
a[i + 1] += (a[i] / 10);
a[i] %= 10;
}
}
void div() {
int i, j, cf, st, tp;
la = strlen(a);
for(i = 0; i < la; ++i) a[i] -= '0';
st = 0;
lb = 0;
while(a[la - 1] || st < la) {
if(a[la - 1] & 1) b[lb++] = 1;
else
b[lb++] = 0;
cf = 0;
for(j = st; j < la; ++j) {
tp = cf * 10 + a[j];
a[j] = tp >> 1;
cf = tp & 1;
}
if(!a[st]) st++;
}
memset(a, 0, sizeof(a));
for(i = 0; i < lb; ++i)
if(b[i]) pw(lb - i - 1);
while(!a[la - 1]) la--;
}
int main() {
while(~scanf("%s", a)) {
if(!strcmp(a, "0")) puts("0");
else {
div();
for(int i = la - 1; i >= 0; --i) printf("%d", a[i]);
puts("");
}
}
return 0;
} 3. 最小邮票数
01背包。。一开始NC忘记判输出0的情况了。。WA*n
//2007年清华大学计算机研究生机试题 最小邮票数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int n, m, dp[1000], w[100];
int main() {
int i, j;
while(~scanf("%d", &m)) {
scanf("%d", &n);
for(i = 0; i < n; ++i) scanf("%d", &w[i]);
for(i = 1; i <= m; ++i) dp[i] = INF;
dp[0] = 0;
for(i = 0; i < n; ++i) {
for(j = m; j >= w[i]; --j) {
if(dp[j - w[i]] == INF) continue;
else
dp[j] = min(dp[j], dp[j - w[i]] + 1);
}
}
if(dp[m] == INF) puts("0");
else
printf("%d\n", dp[m]);
}
return 0;
}