Posted on 2011-09-25 23:45
Uriel 閱讀(454)
評論(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;
}