F(0)=0 F(1)=1 F(2)=2 F(N)=F(N-1)+F(N-2)+F(N-3) N>3 语言用c或者c++...
发布网友
发布时间：2024-01-05 05:22
我来回答
共5个回答
热心网友
时间：2024-08-02 17:16
【程序】
# include
int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];
int exitn(int i,int j,int s,int a[ ])
{ int i1,j1,k,count;
for (count=k=0;k<8;k++)
{ i1=i+delta_i[(s+k)%8];
j1=i+delta_j[(s+k)%8];
if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)
a[count++]=(s+k)%8;
}
return count;
}
int next(int i,int j,int s)
{ int m,k,mm,min,a[8],b[8],temp;
m=exitn(i,j,s,a);
if (m==0) return –1;
for (min=9,k=0;k
{ temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
if (temp
{ min=temp;
kk=a[k];
}
}
return kk;
}
void main()
{ int sx,sy,i,j,step,no,start;
for (sx=0;sx<8;sx++)
for (sy=0;sy<8;sy++)
{ start=0;
do {
for (i=0;i<8;i++)
for (j=0;j<8;j++)
board[j]=0;
board[sx][sy]=1;
I=sx; j=sy;
For (step=2;step<64;step++)
{ if ((no=next(i,j,start))==-1) break;
I+=delta_i[no];
j+=delta_j[no];
board[j]=step;
}
if (step>64) break;
start++;
} while(step<=64)
for (i=0;i<8;i++)
{ for (j=0;j<8;j++)
printf(“%4d”,board[j]);
printf(“\n\n”);
}
scanf(“%*c”);
}
}
七、分治法【问题】 大整数乘法
问题描述：
通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运
算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很
大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小
，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，
就必须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算
法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作
O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。
图6-3 大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位（为简单起见，假设n是2的幂），如图6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
如果按式（1）计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法（
分别对应于式（1）中的加号），此外还要做2次移位（分别对应于式（1）中乘2n和乘2n/2）。所有这些加法和移
位共用O（n）步运算。设T（n）是2个n位整数相乘所需的运算总数，则由式（1），我们有：
（2）
由此可得T（n）=O（n2）。因此，用（1）式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算
复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
虽然，式（3）看起来比式（1）复杂些，但它仅需做3次n/2位整数的乘法（AC，BD和（A-B）（D-C）），6次加、
减法和2次移位。由此可得：
（4）
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式（3），并考虑到X和Y的符号对结果
的影响，我们给出大整数相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}
begin
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左边n/2位;
B=X的右边n/2位;
C=Y的左边n/2位;
D=Y的右边n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
【问题】 最接近点对问题
问题描述：
在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解
其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有
最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面
我们着重考虑平面上的最接近点对问题。
最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个
点即可。然而，这样做效率太低，需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2
，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分
治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为 S1和S2的最接近点对未必
就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个
点分别在 S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计
算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足：
T(n)=2T(n/2)+O(n2)
它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们
所有点
热心网友
时间：2024-08-02 17:13
#inchude<iostream.h>
void main()
{ int a.b.c,s;
cout<<"输入abc"<<endl;
cin>>a>>b>>c;
s=a+b+c 后面忘了，等我查到了再回复你。。。。。。
热心网友
时间：2024-08-02 17:11
利用栈，就是定义一个栈后向将0，1,2 入栈，然后可以递归判断
如果n=3 直接 stack[3]=3，入栈
否则 先将n-1,n-2,n-3 三个位置出栈，并用临时变量记录下来，求出stack[n]=stack[n-1]+stack[n-2]+stack[n-3]，然后将这四个值分别入栈。
热心网友
时间：2024-08-02 17:18
使用赤寒轩37的吧，我刚想这么写来着，看着有人回答了。
热心网友
时间：2024-08-02 17:12
楼上用的是递归的方法，但不符合题意。
栈和递归是两种不同的方法，手动栈要比系统递归栈效率高得多。
#include <stdio.h>
#define MAX 1000
struct stack {
int e[MAX];
int top;
};
struct stack s;
int empty()
{
return !s.top;
}
int top()
{
if (!empty()) return s.e[s.top - 1];
else return -1;
}
int push(int a)
{
if (s.top == MAX) return -1;
s.e[s.top++] = a;
return 1;
}
int pop()
{
if (empty()) return -1;
return s.top--;
}
int init()
{
s.top = 0;
}
int F(int a)
{
int result = 0, tmp;
init();
push(a);
while (!empty())
{
if ((tmp = top()) >= 3)
{
pop();
push(tmp - 1);
push(tmp - 2);
push(tmp - 3);
}
else
{
result += tmp;
pop();
}
}
return result;
}
void main()
{
printf("%d\n", F(5));
}
