|
|
Posted on 2011-06-24 23:47 Uriel 閱讀(610) 評論(4) 編輯 收藏 引用 所屬分類: 考研&保研復(fù)試上機(jī)題
發(fā)指啊... 第一次快寫完了結(jié)果傲游掛了... ...直接全部重來啊... ...OMG 這套比2005年的稍難, 不過基本都是小模擬啦, 對ACM菜鳥來說都是大水題~~ 1. 還是A+B 注意題目第三個case, 8的前面全當(dāng)成0, 所以108和8的前兩位看作相同的 我的方法很WS, 因為題目說不超過8位, 就先把不足8位的數(shù)字串補(bǔ)足8位, 高位全填0, 然后從后面開始比較k位就ok了~
 //浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 還是A+B
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int k, s1, s2, l1, l2;
char a[10], b[10];
  int cal(char *s)  {
 int i, t = 0;
for(i = 0; s[i]; ++i) t = t * 10 + s[i] - '0';
return t;
 }
int main() {
int i;
  while(1) {
scanf("%s %s %d", a, b, &k);
if(!strcmp(a, "0") && !strcmp(b, "0")) break;
l1 = strlen(a); l2 = strlen(b);
for(i = 7; i > 7 - l1; --i) a[i] = a[l1 + i - 8];
for(i = 0; i <= 7 - l1; ++i) a[i] = '0';
for(i = 7; i > 7 - l2; --i) b[i] = b[l2 + i - 8];
for(i = 0; i <= 7 - l2; ++i) b[i] = '0';
if(!strncmp(a + 8 - k,b + 8 - k, k)) {
puts("-1");
continue;
 }
s1 = cal(a); s2 = cal(b);
printf("%d\n", s1 + s2);
}
return 0;
}2. 火星A+B 一開始理解錯題意了, 不過應(yīng)該不會有人跟我有一樣NC的理解吧... = = ...就不說了 有點(diǎn)像高精度加法, 一位位加就好了, 注意進(jìn)制, 先打出100以內(nèi)的質(zhì)數(shù)表(保險起見多打了兩個) 開始一處初始化忘了, WA三次才發(fā)現(xiàn)... ... PS: Discuss驚現(xiàn)ECUST-SJTU---ssjia大牛, 各種Orz 2011.09.17 PS: 這題九度上死活過不了啊... 求交流
//浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 火星A+B
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int bas[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
int a[30], b[30], c[30], l1, l2;
char s1[300], s2[300];
int main() {
int i, tn1, tn2, tp;
while(1) {
scanf("%s %s", s1, s2);
if(!strcmp(s1, "0") && !strcmp(s2, "0")) break;
l1 = strlen(s1);
l2 = strlen(s2);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
tn1 = tn2 = 0; tp = 1;
for(i = l1 - 1; i >= 0; --i) {
if(s1[i] == ',') {
tn1++;
tp = 1;
}
else if(isdigit(s1[i])) {
a[tn1] = a[tn1] + tp * (s1[i] - '0');
tp *= 10;
}
}
tp = 1;
for(i = l2 - 1; i >= 0; --i) {
if(s2[i] == ',') {
tn2++;
tp = 1;
}
else if(isdigit(s2[i])) {
b[tn2] = b[tn2] + tp * (s2[i] - '0');
tp *= 10;
}
}
int cf = 0;
for(i = 0; i <= min(tn1, tn2); ++i) {
c[i] = cf + a[i] + b[i];
if(c[i] >= bas[i]) {
cf = c[i] / bas[i];
c[i] %= bas[i];
}
else
cf = 0;
}
for(;i <= max(tn1, tn2); ++i) {
if(i <= tn1) {
c[i] = cf + a[i];
if(c[i] >= bas[i]) {
cf = c[i] / bas[i];
c[i] %= bas[i];
}
else
cf = 0;
}
else if(i <= tn2) {
c[i] = cf + b[i];
if(c[i] >= bas[i]) {
cf = c[i] / bas[i];
c[i] %= bas[i];
}
else
cf = 0;
}
}
c[i] += cf;
if(c[i] >= bas[i]) {
cf = c[i] / bas[i];
c[i] %= bas[i];
}
else
cf = 0;
if(cf) c[++i] = cf;
while(c[i] == 0 && i > 0) --i;
for(; i > 0; --i) printf("%d,", c[i]);
printf("%d\n", c[0]);
}
return 0;
}
3. 還是暢通工程
模板題, 不解釋
//浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 還是暢通工程
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 110
#define INF 0x3f3f3f3f
int n, adj[N][N], lowcost[N], closest[N];
void prim(int c[][N]) {
bool s[N];
s[1] = true;
for(int i = 2; i <= n; ++i) {
lowcost[i] = c[1][i];
closest[i] = 1;
s[i] = false;
}
for(int i = 1; i < n; ++i) {
int mix = INF, j = 1;
for(int k = 2; k <= n; ++k)
if(lowcost[k] < mix && !s[k]) {
mix = lowcost[k];
j = k;
}
s[j] = true;
for(int k = 2; k <= n; ++k)
if(c[j][k] < lowcost[k] && !s[k]) {
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}
int main() {
int i, j, ans, a, b, c;
while(scanf("%d", &n), n) {
for(i = 1; i <= n * (n - 1) / 2; ++i) {
scanf("%d %d %d", &a, &b, &c);
adj[a][b] = adj[b][a] = c;
}
prim(adj);
ans = 0;
for(i = 1; i <= n; ++i) ans += lowcost[i];
printf("%d\n", ans);
}
return 0;
}
4. 統(tǒng)計同成績學(xué)生人數(shù)
大水題, 不解釋
//浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 統(tǒng)計同成績學(xué)生人數(shù)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 1010
int a[N], n, ans;
int main() {
int x, i;
while(scanf("%d", &n), n) {
for(i = 0; i < n; ++i) scanf("%d", &a[i]);
scanf("%d", &x);
ans = 0;
for(i = 0; i < n; ++i)
if(a[i] == x) ans++;
printf("%d\n", ans);
}
return 0;
}
5. 簡單計算器
我的方法比較麻煩... ...設(shè)置兩個棧(偷懶用了STL, 慢就慢吧...||), 一個符號棧, 一個操作數(shù)棧
當(dāng)讀進(jìn)操作數(shù)時, 若符號棧棧頂為*或/, 就馬上計算掉, 彈出操作數(shù)棧棧頂連續(xù)兩個元素和符號棧棧頂, 算好之后結(jié)果壓進(jìn)操作數(shù)棧, 這里注意下運(yùn)算順序, '-','/'都是有計算順序要求的
當(dāng)讀到運(yùn)算符時, 什么都不管, 直接壓進(jìn)符號棧
最后把操作數(shù)棧和符號棧元素全部倒置(稍微想想就知道為什么了, 一開始這里沒想清楚, 單步了好一會兒才發(fā)現(xiàn)... ...), 然后不斷彈出符號棧棧頂符號和操作數(shù)棧頂連續(xù)兩個操作數(shù), 計算完后結(jié)果壓入操作數(shù)棧, 直至符號棧為空.
//浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 簡單計算器
#include<stack>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
double cal(double a, double b, char c) {
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int main() {
int i;
char op[210];
while(gets(op), strcmp(op, "0") != 0) {
i = 0;
stack<double> opa;
stack<char> opr;
while(op[i]) {
if(isdigit(op[i])) {
double tp = 0.0;
while(isdigit(op[i])) {
tp = tp * 10 + op[i] - '0';
++i;
}
opa.push(tp);
if(!opr.empty() && opr.top() == '*') {
opr.pop();
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '*'));
}
else if(!opr.empty() && opr.top() == '/') {
opr.pop();
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '/'));
}
}
else if(op[i] == '+') {
opr.push('+');
++i;
}
else if(op[i] == '-') {
opr.push('-');
++i;
}
else if(op[i] == '*') {
opr.push('*');
++i;
}
else if(op[i] == '/') {
opr.push('/');
++i;
}
else
++i;
}
stack<char>opr1;
stack<double>opa1;
while(!opr.empty()) {
opr1.push(opr.top());
opr.pop();
}
while(!opa.empty()) {
opa1.push(opa.top());
opa.pop();
}
while(!opr1.empty()) {
double t1 = opa1.top(); opa1.pop();
double t2 = opa1.top(); opa1.pop();
opa1.push(cal(t1, t2, opr1.top()));
opr1.pop();
}
printf("%.2lf\n", opa1.top());
}
return 0;
}
2011.09.10 PS: 這題又用了另一種方法做
遇到數(shù)字的時候不處理, 直接壓入操作數(shù)棧, 遇到'*'或'/'時, 操作符棧頂連續(xù)的'*'或'/'都計算掉, 再將自己壓入操作符棧, 遇到'+'或'-'時, 操作符棧里的都能計算掉, 計算完后再將自己壓入操作符棧, 最后將操作符棧從棧頂依次處理即可, 因為此時不會出現(xiàn)多個'+''-', '*''/'相連導(dǎo)致運(yùn)算順序錯誤的情況
本來以為這樣很方便, 結(jié)果代碼比原來長了快一倍... (因為寫得挫... )
其實(shí)像書上那樣加入結(jié)束字符再處理的話代碼應(yīng)該會短一些... 有空再敲一次
//2006年浙江大學(xué)計算機(jī)及軟件工程研究生機(jī)試題 簡單計算器
#include<ctype.h>
#include<stack>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
double cal(double a, double b, char c) {
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int main() {
int i;
char op[220];
while(gets(op), strcmp(op, "0")) {
i = 0;
stack<double> opa;
stack<char> opr;
while(op[i]) {
if(isdigit(op[i])) {
double tp = 0.0;
while(isdigit(op[i])) {
tp = tp * 10 + op[i] - '0';
++i;
}
opa.push(tp);
}
else if(op[i] == '+') {
if(opr.empty()) opr.push('+');
else {
while(!opr.empty()) {
if(opr.top() == '+') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opr.pop();
opa.push(cal(t2, t1, '+'));
}
else if(opr.top() == '-') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '-'));
opr.pop();
}
else if(opr.top() == '*') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '*'));
opr.pop();
}
else if(opr.top() == '/') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '/'));
opr.pop();
}
}
opr.push('+');
}
++i;
}
else if(op[i] == '-') {
if(opr.empty()) opr.push('-');
else {
while(!opr.empty()) {
if(opr.top() == '-') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '-'));
opr.pop();
}
else if(opr.top() == '+') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '+'));
opr.pop();
}
else if(opr.top() == '*') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '*'));
opr.pop();
}
else if(opr.top() == '/') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '/'));
opr.pop();
}
}
opr.push('-');
}
++i;
}
else if(op[i] == '*') {
if(opr.empty()) opr.push('*');
else {
while(!opr.empty()) {
if(opr.top() == '*') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '*'));
opr.pop();
}
else if(opr.top() == '/') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '/'));
opr.pop();
}
else
break;
}
opr.push('*');
}
++i;
}
else if(op[i] == '/') {
if(opr.empty()) opr.push('/');
else {
while(!opr.empty()) {
if(opr.top() == '/') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '/'));
opr.pop();
}
else if(opr.top() == '*') {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, '*'));
opr.pop();
}
else
break;
}
opr.push('/');
}
++i;
}
else
++i;
}
while(!opr.empty()) {
double t1 = opa.top(); opa.pop();
double t2 = opa.top(); opa.pop();
opa.push(cal(t2, t1, opr.top()));
opr.pop();
}
printf("%.2lf\n", opa.top());
}
return 0;
}
Feedback
# re: 浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 回復(fù) 更多評論
2012-03-02 10:49 by
最后把操作數(shù)棧和符號棧元素全部倒置(稍微想想就知道為什么了, 一開始這里沒想清楚, 單步了好一會兒才發(fā)現(xiàn)... ...),
為什么??？還是沒想明白，盼能解答
# re: 浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 回復(fù) 更多評論
2012-03-02 14:16 by
@毛
因為最后只剩加減法，加減法是從左到右依次計算，而在進(jìn)棧時是從左到右進(jìn)棧的，出棧順序與入棧相反，直接出棧一個計算一個的話就變成是從右到左計算了，所以倒置一下。。(不過這種做法很挫就是了。。= =)
# re: 浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 回復(fù) 更多評論
2012-03-02 14:26 by
哦，想通了。一下子腦子短路了，好笨啊?。?！我也想的是這個方法，嘿嘿?？擅看翁峤欢际荳A，看了帖子才知道錯在這了，謝謝~~~
# re: 浙大計算機(jī)研究生復(fù)試上機(jī)考試-2006年 回復(fù) 更多評論
2012-03-02 14:30 by
@毛
表示我當(dāng)時debug了半天才發(fā)現(xiàn)。。= =
感覺做題之前還是該拿筆算算，想想清楚。。
|