求肋高手来帮解决一下算法设计与分析几道题目
《算法设计与分析》
设计程序完成以下题目，并分析你的程序的时间和空间复杂性
一、 输出m个元素中取n个元素的所有排列。
二、输出m个元素中取n个元素的所有组合。
三、错排问题。输出序列1，2，…，n的所有排列中满足元素i(1≤i≤n)不在第i个位置的排列。
四、输入n，表示有n级楼梯，一次踏步允许走1或2级，问n级楼梯有几种走法。
例：n=2，有2种走法；n=3，有3种走法。
五.输入n行，每行有两个元素，第一个表示元素值，第2个表示该元素个数。求从这些元素取m个元素的所有组合(排列数)。
例：n=3
2，3
4，1
5，2
求(2‚2‚2‚4‚5‚5)中取m=3个元素的组合(排列)
比较各种排序算法的时间及空间复杂性。
下面程序段的时间复杂度为____c ____。
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
a[i][j] = i*j;
A．O(m2) B．O(n2) C．O(m*n) D．O(m+n)
5．执行下面程序段时，执行S语句的次数为___a______。
for (int i=1; i<n; i++)
for (int j=1; j<i; j++)
S;
A．n2 B．n2/2 C．n(n+1) D．n(n+1)/2
6．下面算法的时间复杂度为_________。
int f(unsigned int n) {
if (n==0) || n==1) return 1;
else return n*f(n-1);
}
A．O(1) B．O(n) C．O(n2) D．O(n!)
程序段的时间复杂度为___c_____。
int i=0 , s=0;
while (++i<=n) {
int p=1;
for (int j=1; j<=i; j++) p*= j;
s = s+p;
}
(1) char Compare(SimpleType x1 , SimpleType x2)
{
if (x1>x2) return ‘>’;
else if (x1==x2) return ‘=’;
else return ‘<’;
}
时间复杂度：O(1)。
(2) void Reverse(char * p)
{
int n = strlen(p);
for (int i=0; i<n/2; i++) {
char ch = p[i]
p[i] = p[n-i-1];
p[n-i-1] = ch;
}
}
时间复杂度：O(n)。
(3) double Product(double a [ ] , int n)
{
double p = 1;
for (int i=0; i<n; i++) p *= a[i];
return p;
}
时间复杂度：O(n)。
指出下列各算法的功能，并求出其时间复杂度。
(1) int Prime(int n)
{
int i = 1;
int x = (int)sqrt(n);
while (++i<=x)
if (n%i == 0) break;
if (i>x) return 1;
else return 0;
}
(2) int sum1(int n)
{
int p = 1 , s = 0;
for (int i=1; i<=n; i++) {
p *= i;
s += p;
}
return s;
}
(3) int sum2(int n)
{
int s = 0;
for (int i = 1; i<=n i++) {
int p = 1;
for (int j=1; j<=i; j++)
p *= j;
s += p;
}
return s;
}
(4) int fun(int n)
{
int i=1 , s=1;
while (s<n)
s += ++i;
return i;
}
(5)void UseFile(ifstream & inp , int c[10])
// 假定inp所对应的文件中保存有n个整数
{
for (int i=0; i<10; i++)
c[i] = 0;
int x;
while (inp>>x) {
i = x%10;
c[i]++;
}
}
(6) void mtable(int n)
{
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++)
cout <<i<<"*"<<j<<"="<<setw(2)<<i*j<<" ";
cout <<endl;
}
}
(7) void cmatrix(int a[M][N] , int d)
// M和N为全局整型常量
{
for (int i=0; i<M; i++)
for (int j=0; j<N; j++)
a[i][j] *= d;
}
(8) void matrimult(int a[M][N] , int b[N][L] , int c[M][L])
// M，N和L均为全局整型常量
{
int i , j , k ;
for (i=0; i<M; i++)
for (j=0; j<N; j++)
c[i][j] = 0;
for (i=0; i<M; i++)
for (j=0; j<L; j++)
for (k=0; k<N; k++)
a[i][j] += a[i][k]*b[k][j];
}
问题点数：20、回复次数：3Top
1 楼wanfustudio（雁南飞：知识之败,慕虚名而不务潜修也）回复于 2006-06-02 13:54:41 得分 0
考试啊？
5555555555555555Top
2 楼mLee79（）回复于 2006-06-02 22:01:12 得分 0
作业贴,鉴定完毕..Top
3 楼boxban（冻酸梨）回复于 2006-06-02 23:13:54 得分 0
四、输入n，表示有n级楼梯，一次踏步允许走1或2级，问n级楼梯有几种走法。
例：n=2，有2种走法；n=3，有3种走法。
-------------------------------------
实际上就是费波纳契函数：
F(2) = 2
F(3) = 3
F(n) = F(n-1) + F(n-2)Top
