蓝桥杯2011决赛c本科试题及答案

要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。

相关的工程文件不要拷入。

对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c++特性； 不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。 解答：

最小公倍数就是所有质数的相应幂的积 比如N=10

小于10的质数有2,3,5,7 对应的最大幂是：3，2，1，1

则最小公倍数是：2^3x3^2x5^1x7^1 = 2520

#include #include #include using namespace std;

int a[50] = {0};//存素数 bool vis[100];

int b[50] = {0};//存幂次

void init_prim()//求小于100的所有素数存入数组a {

int i,j,k;

int m = (int)(sqrt(100.0)+0.5); memset(vis,0,sizeof(vis)); vis[0] = 1;

vis[1] = 1;//必须加上,否则第一个素数别认为是1 for(i=2; i<=m; i++) if(!vis[i]) {

for(j=2*i; j<=100; j+=i) vis[j] = 1; }

int t = 0;

for(k=0; k<100; k++) if(!vis[k])

a[t++] = k; }

int main() {

int i,j,k;

第 5/20 页

init_prim(); int n;

//2^6 = 64,2^7 = 128;由于n最大100，幂次最大6 // for(i=0 ; i<100; i++)//素数没问题 // if(!vis[i])

// cout<>n) {

memset(b,0,sizeof(b));

for(i=0; i<=n&&a[i]<=n; i++)//”1到n素数个数小于n的一半 “不对，3有两个素数

{

// cout<

if(pow((double)a[i],(double)j)>(double)n) {

b[i] = j -1;//b的下标不必新开 break; }

else if(pow((double)a[i],(double)j) == (double)n)//必须分开 {

b[i] = j; break; }

} }

//不知道是不是pow函数的问题，把ans定义为int得出的结果出问题，double就对了

double ans = 1; for(k=0; k

//cout<

cout<<(int)ans<

return 0; }

//该程序 到25时就溢出，ans换位long long前几个就错误啦，此时需要把pow函数换掉

#include

第 6/20 页

#include #include #include using namespace std;

const int N = 105; int n;

int a[N][50]; int b[N] = {0};

void multiply() {

int i,j,k;

memset(a,0,sizeof(a)); for(i=3; i<=100; i++) {

/*

下面的是直接按平常的乘法，乘数的一位乘以被乘数的每一位并处理进位；另外是乘数整体乘以被乘数的每一位最后统一处理进位 */

int temp = 0;

a[i][0] = 1;//很重要 for(j=2; j<=i; j++) {

int c = 0;

for(k=0; k<50; k++)//最大不超过160位 ，目前是100!,最后除以3等50 {

temp = a[i][k]*b[j] + c; a[i][k] = temp00; c = temp/1000; } } } }

void printData(int n) {

int i,j,k;

for(i=49; i>=0; i--) if(a[n][i]) break;

cout<=0; j--)

printf(\

第 7/20 页

cout<

int main() {

int i, j, k;

for(i=0; i

for(j=i+1; j<=N; j++) {

if(b[j]%b[i]==0) b[j] /= b[i]; //cout<

//for(i=0; i<100; i++) // cout<

while(cin>>n) {

if(n==1||n==2) {

cout<

printData(n); }

return 0; }

4. 程序设计（满分28分）

为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。

线1 苹果园 .... 四惠东

第 8/20 页