编程算法题

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");
}