[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战 - C++教室 - C++论坛

第 101 楼

也有事，空了研究。
UP

Ｆight ｔｏｗin or ｄie...

第 102 楼

// 10.cpp author:laigaoat2005 data:2007.6.25
#include "iostream.h"
int main()
{
int input=0,count=0;
int i=0;
int ex=1;
while(ex)
{
cout<<"请输入每排正方形的个数：";
cin>>input;
for(i=input;i>0;i--)
{
count+=i*i;
}
cout<<"\n正方形个数是："<<count<<"\n";
input=0;
cout <<"请输入小正方形的边长：";
cin>>input;
count=input*input*count;
cout<<"大正方形的面积是："<<count<<"\n请选择你的操作：输入0退出，输入其它数值继续";
cin>>ex;
}
return 0;
}

没有签名

第 103 楼

/*---------------------------------------------------------------------------
File name: C76-37.cpp
Author: HJin
Created on: 6/25/2007 01:12:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 37:

37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
K1*K2*....*Kn 为最大。
例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大

Analysis:

Do your math to establish the following recurrence formula

f(M, N) = M/N * f(M-M/N, N-1), if N>1
= M, if N=1.

My implementation is just a restating of this formula
in C++ language. You may want to develop an iterative soln.

Sample output:

M = 60, N = 17
max product 1719926784 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 4 * 4 * 4 * 4 * 4 * 4 *
4 * 4 * 4.
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
http://bbs.bc-cn.net/viewthread.php?tid=147853

#include <iostream>
#include <stdexcept>

using namespace std;

long f(int M, int N, int *k);

int main(int argc, char** argv)
{
int i;
int M=60;
int N=17;
int prod;
int* k = new int[N];

prod = f(M, N, k);

cout<<"M = "<<M<<", N = "<<N<<endl;

cout<<"max product "<<prod<<" = ";
for(i=0; i<N-1; ++i)
cout<<k[i]<< " * ";
cout<<k[N-1]<<"."<<endl;

delete [] k;

return 0;
}

long f(int M, int N, int* k)
{
static int index = 0;
if(M<N)
return 0;

if(N==1)
{
k[index] = M;
return M;
}
else
{
k[index] = M/N;
++index;
return M/N * f(M-M/N, N-1, k);
}
}

I am working on a system which has no Chinese input. Please don\'t blame me for typing English.

第 104 楼

/*---------------------------------------------------------------------------
File name: C76-67.cpp
Author: HJin
Created on: 6/25/2007 02:03:08
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 67 :

67. ( NOI'94.1_3 ) 一个实数数列共有Ｎ项，已知a(i)=(a(i-1)-a(i+1))/2+d，
（１〈i〈Ｎ）(N<60) , 键盘输入Ｎ，d，a(1)，a(n)，m，输出 a(m)。

Analysis:

A littl bit algebra shows that we are solving a tridiagonal linear
system (refer to you linear algebra textbook for solving Ax = b).

The tridiagonal linear system solver is standard and has been know
for almost 200 years.

Sample output:

i | a[i] | (a[i-1] - a[i+1]) / 2 + d
-----+----------------------+------------------------------
1 | 0 |
2 | 0.585786 | 0.585786
3 | 0.828427 | 0.828427
4 | 0.928932 | 0.928932
5 | 0.970563 | 0.970563
6 | 0.987807 | 0.987807
7 | 0.994949 | 0.994949
8 | 0.997908 | 0.997908
9 | 0.999133 | 0.999133
10 | 0.999642 | 0.999642
11 | 0.99985 | 0.99985
12 | 0.999942 | 0.999942
13 | 0.999965 | 0.999965
14 | 1.00001 | 1.00001
15 | 0.999939 | 0.999939
16 | 1.00013 | 1.00013
17 | 0.999672 | 0.999672
18 | 1.00079 | 1.00079
19 | 0.998091 | 0.998091
20 | 1.00461 | 1.00461
21 | 0.988873 | 0.988873
22 | 1.02686 | 1.02686
23 | 0.935147 | 0.935147
24 | 1.15657 | 1.15657
25 | 0.622007 | 0.622007
26 | 1.91255 | 1.91255
27 | -1.2031 | -1.2031
28 | 6.31876 | 6.31876
29 | -11.8406 | -11.8406
30 | 32 |
-----+----------------------+------------------------------
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
http://bbs.bc-cn.net/viewthread.php?tid=147853

#include <iostream>
#include <iomanip>

using namespace std;

/**
n --- number of equations
sub --- subdiagonal entries
diag --- diagonal entries
sup --- supdiagonal entries
b --- original rhs vector
x --- solution vector
*/
void triDiagonal(int n,
double* sub,
double* diag,
double* sup,
double* b,
double* x);

int main(int argc, char** argv)
{
int i;
int N=30;
double *a = new double[N];
double d = 1;
int m=5;

a[0] = 0;
a[N-1] = 32;

double* sub = new double[N-2];
double* sup = new double[N-2];
double* diag = new double[N-2];
double* x = &a[1];
double* b = new double[N-2];

for(i=0; i<N-2; ++i)
{
sub[i] = 1.0;
diag[i] = -2.0;
sup[i] = -1.0;
b[i] = -2.0*d;
}
b[0] += -a[0];
b[N-3] += a[N-1];

triDiagonal(N-2, sub, diag, sup, b, x);

//cout<<x[m]<<endl;

cout<<std::left<<setw(4)<<"i"<<" | "<<std::right<<setw(20)<<"a[i]"<<" | "<<std::left<<"(a[i-1] - a[i+1]) / 2 + d"<<endl;
cout<<"-----+----------------------+------------------------------\n";
i=0;
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[0]<<" | "<<std::left<<" "<<endl;
for(i=1; i<N-1; ++i)
{
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[i]<<" | "<<std::left<<setw(20)<<( a[i-1] - a[i+1] )/2.0 + d<<endl;
}
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[N-1]<<" | "<<std::left<<" "<<endl;
cout<<"-----+----------------------+------------------------------\n";

delete [] a;
delete [] sub;
delete [] diag;
delete [] sup;
delete [] b;

return 0;
}

void triDiagonal(int n,
double* sub,
double* diag,
double* sup,
double* b,
double* x)
{
int i;
double factor;

// forward elimination
for (i = 1; i < n; ++i)
{
factor = -sub[i-1] / diag[i-1];
diag[i] += factor * sup[i-1];
b[i] += factor * b[i-1];
}

// backward substitution
x[n-1] = b[n-1]/ diag[n-1];
for(i = n-2; i >=0; --i)
x[i] = (b[i] - sup[i]*x[i+1]) / diag[i];
}

I am working on a system which has no Chinese input. Please don\'t blame me for typing English.

第 105 楼

/*---------------------------------------------------------------------------
File name: C76-74.cpp
Author: HJin
Created on: 6/25/2007 04:45:37
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 74 :

74. (NOI'95.1_5) m、n为整数，且满足下列两个条件：
　　① m、n∈｛1, 2, …, k｝, (1≤k≤109)
② (n^2－m*n－m^2)^2＝1
编一程序, 由键盘输入k, 求一组满足上述两个条件的 m、n, 并且使m^2＋n^2
的值最大.
例如, 若 k＝1995, 则 m＝987, n＝1597 时, 则 m、n 满足条件, 且可使
m^2＋n^2的值最大.

Analysis:

Loop over m and n, O(k^2) algorithm.

Sample output:

3524578
m = 987, n = 1597, m^2 + n^2 = 3524578
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
http://bbs.bc-cn.net/viewthread.php?tid=147853

#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char** argv)
{
int m;
int n;
int temp;
int tempSquare;
int max=2;
int k=1995;
int mKeeper=1;
int nKeeper=1;

/**
O(k^2) algorithm --- just a 2-loop.
*/
for(m=1; m<=k; ++m)
{
for(n=1; n<=k; ++n)
{
temp = n*(n-m)-m*m;
if(temp*temp == 1)
{
tempSquare=m*m+n*n;
if(max < tempSquare)
{
max = tempSquare;
mKeeper = m;
nKeeper = n;
}
}
}
}

cout<<max<<endl;
cout<<"m = "<<mKeeper<<", n = "<<nKeeper<<", m^2 + n^2 = "<<mKeeper*mKeeper + nKeeper*nKeeper<<endl;

return 0;
}

I am working on a system which has no Chinese input. Please don\'t blame me for typing English.

第 106 楼

To 野比：

HCL's #6 tested to be correct (at least for n = 5, 4).

To HCL:

If you could write some comments about your idea inside the source code, that would be better for a viewer to follow the algorithm (instead of just copying your souce code).

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
Enter a number : 5
25 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

1 3 4 10 11
2 5 9 12 19
6 8 13 18 20
7 14 17 21 24
15 16 22 23 25

1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9

Press any key to continue . . .

Enter a number : 4
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

1 3 4 10
2 5 9 11
6 8 12 15
7 13 14 16

1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7

Press any key to continue . . .

[此贴子已经被作者于2007-6-26 3:20:39编辑过]

I am working on a system which has no Chinese input. Please don\'t blame me for typing English.

第 107 楼

我看第4题这个简单的没人挑啊。。。

程序代码：

int fun(int n) { for(int i=1;i<=n;i++) { for(int j=i;j<i+n;j++) cout<<(j-1)%n+1<<" "; cout<<endl; } } void main() { fun(5); }

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分！

第 108 楼

第三题，C++：

程序代码：

#include<iostream> using namespace std; void print(int,int,int); int n; int main() { cin>>n; if(n>=20||n<=3) return 0; int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==1||i==n||j==1||j==n) cout<<"T"; else if(i==2||i==n-1||j==2||j==n-1) cout<<"J"; else print(1,i,j); } cout<<endl; } system("pause"); } void print(int a,int i,int j) { if(a>n) return; if(i-2==a||i==n-a-1||j-2==a||j==n-a-1) cout<<a; else print(a+1,i,j); return; }

第 109 楼

第九题：

程序代码：

#include<iostream> using namespace std; #define N 16 #define f(n1,n2,n3,n4) {n1/=2;n2/=2;n3/=2;n4+=n1+n2+n3;} int main() { int a,b,c,d; a=b=c=d=N; f(a,b,c,d); f(b,c,d,a); f(c,d,a,b); f(d,a,b,c); cout<<a<<endl<<b<<endl<<c<<endl<<d<<endl; system("pause"); return 0; }

第 110 楼

第8题：
不知道是不是下面的意思?

程序代码：

#include <cmath> template<class T> class BYTE { char *ptr; unsigned num; public: BYTE() { num=sizeof(T)*8; ptr=new char[num]; if(!ptr)return; memset(ptr,0,num); } BYTE(T t) { num=sizeof(T)*8; ptr=new char[num]; if(!ptr)return; memset(ptr,0,num); for(int i=0;i<num;i++) ptr[i]=(t&(T)pow(2,i))==0?0:1; } BYTE(const BYTE<T>& byte) { num=byte.num; ptr=new char[num]; if(!ptr)return; memset(ptr,0,num); for(int i=0;i<num;i++) ptr[i]=byte.ptr[i]; } ~BYTE() { num=0; delete[]ptr; } BYTE<T>& operator=(BYTE<T>& byte) { memset(ptr,0,num); for(int i=0;i<num;i++) ptr[i]=byte.ptr[i]; return *this; } BYTE<T>& operator=(T t) { *this=BYTE<T> byte(t); return *this; } BYTE operator+(BYTE<T> bt) { BYTE<T> temp; char t=0; for(int i=0;i<num;i++) { temp.ptr[i]=(t+ptr[i]+bt.ptr[i])%2; t=(t+ptr[i]+bt.ptr[i])/2; } return temp; } BYTE operator|(BYTE<T> bt) { BYTE<T> temp; char t=0; for(int i=0;i<num;i++) { temp.ptr[i]=(t+ptr[i]+bt.ptr[i])%2; t=(t+ptr[i]+bt.ptr[i])/2; } return temp; } operator T() { return GetValue(); } T GetValue() { T data; memset(&data,0,sizeof(T)); for(int i=0;i<num;i++) { data|=T(int(ptr[i])*pow(2,i)); } return data; } friend ostream& operator<<(ostream &os,BYTE<T>& byte) { for(int i=byte.num-1;i>=0;i--) os<<char(byte.ptr[i]+48); os<<endl; return os; } };

测试用例

程序代码：

void main() { // fun(5); BYTE<int> a=3; BYTE<int> b=3; cout<<b<<endl; cout<<a<<endl; cout<<b+a<<endl; cout<<(b|a)<<endl; cout<<b.GetValue()<<endl; int c=b; cout<<c<<endl; // string s1="1"; }

[glow=255,red,2]wfpb的部落格[/glow] 学习成为生活的重要组成部分！

全能ASP/PHP/ASP.NET主机，支持月付	专业 MSSQL 数据库空间，支持月付	专业 MySQL 数据库空间，支持月付	买域名，送MP3、MP4
高端软件开发 = 年薪十万不是梦	赛孚耐:软件保护加密专家	身份认证令牌USB KEY	买空间，免费送域名（厦门中资源）