編程演算法題

A. 編程演算法題：將兩個數組a、b中相同的元素提取出來，保存在數組c中，不考慮空間復雜度。

有nlogn的,先對兩個數組進行排序,然後再拿其中的一個數字去另一個數字中二分查找.

B. 一道編程演算法題

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define EPS 1E-6

typedef struct item {
double coefficient;
int power;
struct item *next;
} *POLYNOMIAL,*pItem;

POLYNOMIAL Create() { // 創建多項式
pItem head,p;
double coe;
int pwr,iterms,i;
head = p = (pItem)malloc(sizeof(struct item));
scanf("%d",&iterms); // 讀入多項式的項數
for(i = 0; i < iterms; ++i) {
scanf("%lf%d",&coe,&pwr);
p->next = (pItem)malloc(sizeof(struct item));
p->next->coefficient = coe;
p->next->power = pwr;
p = p->next;
}
p->next = NULL;
return head;
}

void Sort(POLYNOMIAL head) { // 按冪次降排序
pItem pt,q,p = head;
while(p->next) {
q = p->next;
while(q->next) {
if(p->next->power < q->next->power) {
pt = p->next;
p->next = q->next;
q->next = p->next->next;
p->next->next = pt;
}
else q = q->next;
}
p = p->next;
}
}

void Show(POLYNOMIAL head) { // 顯示
POLYNOMIAL p = head->next;
int flag = 1;
if(p == NULL) return;
while(p) {
if(flag) {
if(fabs(p->coefficient) >= EPS) {
if(p->power == 0) printf("%.2lf",p->coefficient);
else if(p->power == 1) {
if(p->coefficient == 1.0) printf("x ");
else if(p->coefficient == -1.0) printf("-x ");
else printf("%.2lfx ",p->coefficient);
}
else if(p->coefficient == 1.0) printf("x^%d ",p->power);
else if(p->coefficient == -1.0) printf("-x^%d ",p->power);
else printf("%.2lfx^%d ",p->coefficient,p->power);
flag = 0;
}
}
else if(p->coefficient > 0.0 && fabs(p->coefficient) >= EPS) {
if(p->power == 0) printf("+ %.2lf ",p->coefficient);
else if(p->power == 1) {
if(p->coefficient == 1.0) printf("+ x ");
else printf("+ %.2lfx ",p->coefficient);
}
else if(p->coefficient == 1.0) printf("+ x^%d ",p->power);
else printf("+ %.2lfx^%d ",p->coefficient,p->power);
}
else if(p->coefficient < 0.0 && fabs(p->coefficient) >= EPS) {
if(p->power == 0) printf("- %.2lf ",-p->coefficient);
else if(p->power == 1) {
if(p->coefficient == -1.0) printf("- x ");
else printf("- %.2lfx ",-p->coefficient);
}
else if(p->coefficient == -1.0) printf("- x^%d ",-p->power);
else printf("- %.2lfx^%d ",-p->coefficient,p->power);
}
p = p->next;
}
printf("\n");
}

double Power(double x,int n) {
double value = 1.0;
int i;
for(i = 0; i < n; ++i) value *= x;
return value;
}

double Value(POLYNOMIAL head,double x) { // 多項式求值
POLYNOMIAL p;
double value = 0.0;
for(p = head->next; p; p = p->next)
value += p->coefficient * Power(x,p->power);
return value;
}

POLYNOMIAL Copy(POLYNOMIAL A) {
POLYNOMIAL head,t,p;
head = t = (pItem)malloc(sizeof(struct item));
for(p = A->next; p; p = p->next) {
t->next = (pItem)malloc(sizeof(struct item));
t->next->coefficient = p->coefficient;
t->next->power = p->power;
t = t->next;
}
t->next = NULL;
return head;
}

POLYNOMIAL Additive(POLYNOMIAL A, POLYNOMIAL B) { // 多項式加
POLYNOMIAL head,p,q,t;
head = Copy(A);
for(p = B; p->next; p = p->next) {
q = head;
while(q->next) {
if(p->next->power == q->next->power) {
q->next->coefficient += p->next->coefficient;
if(fabs(q->next->coefficient) <= EPS) {
t = q->next;
q->next = t->next;
free(t);
}
break;
}
q = q->next;
}
if(q->next == NULL) {
q->next = (pItem)malloc(sizeof(struct item));
q->next->coefficient = p->next->coefficient;
q->next->power = p->next->power;
q->next->next = NULL;
}
}
Sort(head);
return head;
}

POLYNOMIAL Subtract(POLYNOMIAL A, POLYNOMIAL B) { // 多項式減
POLYNOMIAL head,p,q,t;
head = Copy(A);
for(p = B; p->next; p = p->next) {
q = head;
while(q->next) {
if(p->next->power == q->next->power) {
q->next->coefficient -= p->next->coefficient;
if(fabs(q->next->coefficient) <= EPS) {
t = q->next;
q->next = t->next;
free(t);
}
break;
}
q = q->next;
}
if(q->next == NULL) {
q->next = (pItem)malloc(sizeof(struct item));
q->next->coefficient = -p->next->coefficient;
q->next->power = p->next->power;
q->next->next = NULL;
}
}
Sort(head);
return head;
}

POLYNOMIAL Multiplication(POLYNOMIAL A, POLYNOMIAL B) { // 多項式乘
POLYNOMIAL head,t,p,q;
head = t = (pItem)malloc(sizeof(struct item));
for(p = A->next; p; p = p->next) { // 完成相乘過程
for(q = B->next; q; q = q->next) {
t->next = (pItem)malloc(sizeof(struct item));
t->next->coefficient = p->coefficient * q->coefficient;
t->next->power = p->power + q->power;
t = t->next;
}
}
t->next = NULL;
Sort(head); // 排序
p = head;
while(p->next) { // 合並同類項
q = p->next;
while(q->next) {
if(p->next->power == q->next->power) {
p->next->coefficient += q->next->coefficient;
t = q->next;
q->next = t->next;
free(t);
}
else q = q->next;
}
p = p->next;
}
return head;
}

void FreeMemory(POLYNOMIAL head) {
POLYNOMIAL q,p = head;
while(p) {
q = p;
p = q->next;
free(q);
}
}

int main() {
char ops[3];
POLYNOMIAL A,B,C = NULL,D = NULL,E = NULL;
printf("創建多項式A:\n");
printf("多項式A的項數:");
A = Create();
Sort(A);
printf("A(x) = ");Show(A);
printf("創建多項式B:\n");
printf("多項式B的項數:");
B = Create();
Sort(B);
printf("B(x) = ");Show(B);
printf("運算符 : ");
fflush(stdin);
gets(ops);
for(int i = 0; ops[i]; ++i) {
switch(ops[i]) {
case '+' : C = Additive(A,B);
printf("C(x) = ");
Show(C);
break;
case '-' : D = Subtract(A,B);
printf("D(x) = ");
Show(D);
break;
case '*' : E = Multiplication(A,B);
printf("E(x) = ");
Show(E);
break;
default : printf("不能識別運算符 : %s\n",ops[i]);
}
}
printf("A(2) = %.2lf\n",Value(A,2.0));
printf("B(2) = %.2lf\n",Value(B,2.0));
if(C) {
printf("C(2) = %.2lf\n",Value(C,2.0));
FreeMemory(C);
}
if(D) {
printf("D(2) = %.2lf\n",Value(D,2.0));
FreeMemory(D);
}
if(E) {
printf("E(2) = %.2lf\n",Value(E,2.0));
FreeMemory(E);
}
FreeMemory(A);
FreeMemory(B);
return 0;
}

C. 兩道編程演算法題（兩圖一道），題目如下，可以給出演算法思路或者源代碼，源代碼最好是C語言的

就會個第一題(因為第一題上已經給出了大致思路)

思路:用map容器(它的內部數據結構是一顆紅黑樹，查找和插入數據速度非常快)
map<int,st>a;//key(int)：設置為1~n的數;value(st):設置為key的前驅和後繼；

這樣一來就可以像鏈錶快速插入數據，又可以像數組隨機訪問元素(key,就相當於數組的下標)

下面是代碼和運行截圖；

看代碼前建議先了解一下map容器的具體用法;

#include<iostream>

#include<map>

#include<vector>

using namespace std;

struct st{//兩個成員變數用來儲存前驅和後繼

int left;//0

int right;//1

st()

{

left=0;

right=0;

}

};

void input(map<int,st> &a)//輸出

{

st t;

int s=0;

map<int,st>::iterator it;//迭代器(指針)

for(it=a.begin();it!=a.end();it++)//循環迭代

{

t=it->second;

if(t.left==0)//左邊等於0,說明該數是第一個數

{

s=it->first;//記錄key

break;

}

}

t=a[s];

cout<<s<<" ";

while(t.right!=0)//循環找當前數的右邊的數(右邊的為0，就說明該數是最後一個數)

{

cout<<t.right<<" ";

t=a[t.right];

}

}

int main()

{

st t,t_i,t_x,t_k,s;

map<int,st>a;

map<int,st>::iterator it;

int n,x,p,x_l,x_r;

cin>>n;

for(int i=1;i<=n;i++)//map容器賦初值(i,t)

//i:(key)下標;t:(value)結構體變數

{

a.insert(make_pair(i,t));

}

for(int i=2;i<=n;i++)

{

cin>>x>>p;

if(p==0)//x的左邊插入i

{

t=a[x];

if(t.left==0)//x的左邊沒有數

{

t_x.left=i;

t_i.right=x;

a[x]=t_x;

a[i]=t_i;

}

else//x的左邊有數

{

int x_left;

t_x=a[x];

x_left=t_x.left;

t_k=a[x_left];

t_i.right=x;

t_i.left=t_x.left;

t_k.right=i;

t_x.left=i;

a[x]=t_x;

a[i]=t_i;

a[x_left]=t_k;

}

}

else//x的右邊插入i

{

t=a[x];

if(t.right==0)//x的右邊沒有數

{

t_x.right=i;

t_i.left=x;

a[x]=t_x;

a[i]=t_i;

}

else//x的左邊有數

{

int x_right;

t_x=a[x];

x_right=t_x.right;

t_k=a[x_right];

t_i.left=x;

t_i.right=t_x.right;

t_k.left=i;

t_x.right=i;

a[x]=t_x;

a[i]=t_i;

a[x_right]=t_k;

}

}

}

for(it=a.begin();it!=a.end();it++)//循環迭代列印各個數之間的關系

{

cout<<it->first<<" ";

cout<<"左邊:";

cout<<it->second.left<<" ";

cout<<"右邊:";

cout<<it->second.right<<endl;

}

input(a);//列印序列

return 0;

}

/*

4

1 0

2 1

1 0

2 3 4 1

*/

D. 兩道簡單的C語言編程題 1.設給定三個整數a.b.c,試寫出尋找其中數的一個演算法，並分析在平均情況

先回答第一個問題：

#include<stdio.h>
#include<conio.h>
intmain(){
inta,b,c,d;
printf("Inputa,b,c:");
scanf("%d,%d,%d",&a,&b,&c);
if(a>=b){
if(b>=c)d=b;//a>=b>=c，比較2次
elseif(a>=c)d=c;//a>=c>b，比較3次
elsed=a;//c>a>=b，比較3次
}else{
if(a>=c)d=a;//b>a>=c，比較2次
elseif(b>=c)d=c;//b>=c>a，比較3次
elsed=b;//c>b>a，比較3次
}//平均比較次數：(2+3+3+2+3+3)/6=8/3次，最壞比較次數：3次
printf("ZhongShu=%d
Finished!
",d);
getch();
return0;
}

平均比較8/3次，最壞比較3次。第二個問題：

#include<stdio.h>
#include<conio.h>
intBinMax(inta[],intlow,inthigh){//二分查找最大值，low、high為查找范圍下標
if(low>high){
printf("
BinMaxError!
");
return-32768;//范圍出錯，提示，並返回整型最小值
}
if(low==high)returna[low];
if(low==high-1)return(a[low]>a[high]?a[low]:a[high]);
intmid=(low+high)/2,m1,m2;
m1=BinMax(a,low,mid);//找前半部的最大值
m2=BinMax(a,mid+1,high);//找後半部的最大值
return(m1>m2?m1:m2);
}
intmain(){
inta[9]={3,6,2,5,9,1,8,7,10},max;//元素個數不一定要滿足n=2^k
max=BinMax(a,0,8);
printf("max=%d
Finished!
",max);
getch();
return0;
}

都能看懂吧？希望能幫到你！

E. 數據結構與演算法設計編程題（用C++描述），急，求大神解答~~~

以待排序序列 { 2， 5， 3， 4， 1} 為例，按非遞減有序排列。

第一趟起泡排序過程如下：

初始：25341
第1次：25341
第2次：235413比最終位置前移了一個位置
第3次：234514比最終位置前移了一個位置
第4次：23415

通過第一趟的排序過程發現，3、4原來在索引為2、3的位置，但經過第一趟排序過程後，3、4暫時移動到了索引為1、2的位置。

C++程序如下：

#include"iostream"
#include"iomanip"

usingnamespacestd;

//輸出數組中的所有元素
voiddisplay(intarr[],intn)
{
	inti;

	for(i=0;i<n;i++)
	{
		cout<<setw(4)<<arr[i];
	}
	cout<<endl;
}

//起泡排序
voidbubbleSort(intarr[],intn)
{
	inti,j;
	inttemp;

	for(i=0;i<n-1;i++)
	{
		for(j=0;j<n-1-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}

		cout<<"第"<<i+1<<"趟："<<endl;
		display(arr,n);
	}
}

intmain()
{
intarr[]={2,5,3,4,1};
	intn=5;

	cout<<"初始狀態："<<endl;
	display(arr,n);

	bubbleSort(arr,n);

return0;
}

運行測試：

初始狀態：
25341
第1趟：
23415
第2趟：
23145
第3趟：
21345
第4趟：
12345

F. 計算機演算法題！編程實現5個矩陣A1A2A3A4A5聯乘積

你題目裡面的矩陣有六個 啊 ，而且 5*10，30*20，20*25 不對吧！
我的代碼在下面，你自己改幾個數字吧。 下面標記了
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct matrix{
int row,col,num[40][40];
} a[5];
struct matrix pro(struct matrix a,struct matrix b)
{
struct matrix c;
int i,j,k;
c.row = a.row; c.col = b.col;
memset(c.num,sizeof(c.num),0);
for(i=0;i<c.row;i++)
{
for(j=0;j<c.col;j++)
{
for(k=0;k<a.col;k++)
c.num[i][j] += a.num[i][k] * b.num[k][j];
}
}
return c;
}
void out(struct matrix a)
{
int i,j;
for(i=0;i<a.row;i++)
{
for(j=0;j<a.col;j++)
printf("%5d ",a.num[i][j]);
puts("");
}
}
int main()
{
int i,j,k;
struct matrix ans;
a[0].row = 2; a[0].col = 3; /*設置行和列*/
a[1].row = 3; a[1].col =2;
a[2].row = 15; a[2].col = 5;
a[3].row = 5; a[3].col = 10;
a[4].row = 10; a[4].col = 25; /*這里進行更改就行*/
for(i=0;i<5;i++)
{
printf("please enter matrix %d ( %d * %d ):\n",i+1,a[i].row,a[i].col);
for(j=0;j<a[i].row;j++)
{
for(k=0;k<a[i].col;k++)
scanf("%d",&(a[i].num[j][k]));
}
}
for(i=0;i<4;i++)
{
ans = pro(a[i],a[i+1]);
}
puts("answer matrix is :");
out(ans);
system("pause");
}