山东大学计算机导论与程序设计基础实验11-12

标签：11 head 12 ListNode struct int 链表山东大学 pNext

A : 实验11 斐波那契序列

题目描述

使用递归法求斐波那契序列第n项的值。
斐波那契序列的定义：

f ( n ) = { 0 , n = 1 1 , n = 2 , n 为自然数 f ( n − 1 ) + f ( n − 2 ) , n > 2 f(n)= \begin{cases} 0, & n=1\\ 1, & n=2,n为自然数\\ f(n-1)+f(n-2),&n>2 \end{cases} f(n)=⎩ ⎨ ⎧0,1,f(n−1)+f(n−2),n=1n=2,n为自然数n>2

输入格式

一个整数N

输出格式

一个整数M，为斐波那契数列第N项。

完整答案代码

#include<stdio.h>
unsigned long long fib(int n){
	static unsigned long long fin;
	if(n==1){
		fin=0;
	}else if(n==2){
		fin=1;
	}else{
		fin=fib(n-1)+fib(n-2);
	}
	return fin;
}
int main()
{
	int n;
	scanf("%d",&n);
	unsigned long long fin=fib(n);
	printf("%d",fin);
	return 0;
 }

B : 实验11 递归折半查找

题目描述

利用递归实现。在一组有n个元素的有序数据中折半查找关键字key，如果找到，返回key所在的位置，否则返回-1。

输入格式

第一行参数N，M；N为这一组数的个数，M为待查找的数；第二行为N个整数，为排序后的数。

输出格式

一个整数J，若能找到，这该整数在数组内的下标，若无法找到，则输出-1；

完整答案代码

#include<stdio.h>
int fin(int a[],int start,int end,int key){
	static int mid;
	static int found;
	if(start>end){
		found=-1;
	}else{
		mid=(start+end)/2;
		if(mid==start||mid==end){
			found=-1;
		}else if(key==a[mid]){
			found=mid;
		}else if(key<a[mid]){
			found=fin(a,start,mid,key);
		}else if(key>a[mid]){
			found=fin(a,mid,end,key);
		}
	}
	return found;
}
int main()
{
	int n,key;
	scanf("%d%d",&n,&key);
	int a[n];
	int i;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int found=fin(a,0,n-1,key);
	printf("%d",found);
	return 0;
}

C : 实验11 递归寻找最大值

题目描述

利用递归法找出一个数组中的最大元素。

输入格式

第一行一个数N，为数组中元素的个数，第二行N个整数，以空格进行分隔，为数组中的元素。

输出格式

一个数M，为数组中的最大元素。

完整答案代码

#include<stdio.h>
int max(int a[],int n){
	static int ma,temp;
	if(n==1){
		ma=a[0];
	}else{
		temp=max(a,n-1);
		if(temp>a[n-1]){
			ma=temp;
		}else{
			ma=a[n-1];
		}
	}
	return ma;
}
int main()
{
	int n;
	scanf("%d",&n);
	int a[n];
	int i;
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	} 
	int ma=max(a,n);
	printf("%d",ma);
	return 0;
}

D : 实验11 递归寻找假币

题目描述

小明有一堆硬币若干枚，其中一枚是假币，外观上这枚假币与真币无法区分，但假币比真币轻（每枚真币的重量都相同）。目前小明手上的工具只有一台天平。
假设硬币有 2 n 2^n 2n枚（n为正整数）。在查找假币的过程中，若要求平均比较次数尽量小，请编程帮小明找出其中的假币，输出假币的编号，并分析你编写的程序的时间复杂度。

输入格式

第一行一个数N，为题目描述中的n；
之后 2 n 2^n 2n个整数，以空格分隔，为硬币的质量。

输出格式

一个数M，为假币的编号

完整答案代码

#include<stdio.h>
#include<math.h>
int main()
{
	int n;
	scanf("%d",&n);
	int sum=pow(2,n); 
	int a[sum];
	int i;
	for(i=0;i<sum;i++){
		scanf("%d",&a[i]);
	}
	int z;
	if(a[0]==a[1]){
		z=a[0];
	}else{
		z=(a[0]>a[1])?a[0]:a[1];
	}
	i=0;
	while(a[i]==z){
		i++;
	}
	printf("%d",i);
	return 0;
}

E : 实验12 贪心

题目描述

给定n种物品，基于结构体与结构数组，利用贪心法解决0/1背包问题。
贪心策略：优先选择单位重量价值最大的物品装入背包；
定义每件物品的结构：

struct good
{
    int No;      ///物品编号
    float weight;  //物品重量
    float value;   //物品价值
    float pw;    //物品单位重量的价值； pw=value/weight;
}

//提示：
函数原型：void greedy(struct good goods[], int n); // goods[]为n种物品的结构数组；
将n种物品的结构数组goods[]按照物品结构中的pw进行降序排列；
从数组goods[]的第一个元素开始，顺序尝试将数组元素对应的物品装入背包，并依次输出装入背包的物品的相关信息；
当尝试到将某个元素对应的物品装入背包后，背包中物品的总重量大于背包容量，则装包方案即为该元素之前的数组元素对应的所有物品；
最后输出装入背包中物品的总重量与总价值；
测试用例：
背包容量C=150，7种物品，其重量W=(10,40,30,50,35,40,30)，价值V=(35,30,6,50,40,10,25)
贪心法得到的解：装入物品1,5,4,7，背包重量125，最大价值150；
无需考虑结果是否为最优解
不存在两个物品单位重量的价值相同

输入格式

第一行两个数，物品数量n，背包容量C
接下来n行，每行第一个数为重量w，第二个数为价值v，均为整数

输出格式

共两行
第一行为整数W，W为背包中物品的总重量，
第二行为整数V，V为背包中物品的总价值。

完整答案代码

#include<stdio.h>
struct good
{
	float w;
	float v;
	float pw;
}; 
int main()
{
	int n,c;
	scanf("%d%d",&n,&c);
	struct good g[n];
	int i,j;
	int sw=0,sv=0;
	for(i=0;i<n;i++){
		scanf("%f %f",&g[i].w,&g[i].v);
		g[i].pw=g[i].v/g[i].w;
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(g[i].pw<g[j].pw){
				struct good t=g[i];
				g[i]=g[j];
				g[j]=t;
			}
		}
	}
	
	for(i=0;i<n&&c>sw;i++){
		if(c>=(sw+g[i].w)){
			sw+=g[i].w;
			sv+=g[i].v;
		}else{
			break;
		}
	}
	printf("%d\n%d",sw,sv);
	return 0;
 }

F : 实验12 链表相关操作

题目描述

链表的基本操作
定义结构体：

struct ListNode {
    int val;
    struct ListNode *next;
};

函数实现：
（1）给定一组无序整数，按给定数据的顺序建立一个单向链表；返回链表的头指针；
（2）将链表中的结点按数据进行排序，构成一个按数据升序排列的有序单向链表；返回有序链表的头指针。
（3）链表的遍历：按升序输出链表中的所有数据；
函数原型：void output(data *head); //从头指针head开始依次输出链表中的所有数据；
（4）编写链表结点的插入函数。
函数原型：data* insertNode(data *head, int N); //在以head为头指针的升序排列的链表中，将整数N插入到链表的合适位置，使插入后的链表仍为升序排列；返回链表的头指针；
（5）实现链表结点的删除函数：在链表中删除一个结点；
函数原型：data* removeNode(data *head, int N); //在以head为头指针的升序排列的链表中，删除整数N对应的结点，返回链表的头指针；
删除第一个元素为N的节点即可

输入格式

第一行三个整数N,M,G；
N为链表中节点个数，M为将要插入链表中的元素，G为要在链表中删除的元素。
之后N行为初始化的N个元素

输出格式

每次output均为遍历链表中的节点

Hint

本题使用 SDUOJ 的 FunctionTemplate 功能进行答题，你仅需要在函数模板中的 TODO 位置填写实现相应功能的代码即可
函数模板最简单的例子也可以详见题 SDUOJ-1001

本题需要填写的函数模板 (你需要修改的部分，并作为最终要提交的代码) 为：

ListNode* createList(int a[],int n){
  // TODO: 填写创建链表的函数
}
ListNode* sortList(struct ListNode* head){
  // TODO: 填写链表排序的函数
}
void output(ListNode* head){
  // TODO: 填写输出每个节点值的函数
}
ListNode* insertNode(ListNode* head,int n){
  // TODO: 填写向有序链表插入值的函数
}
ListNode* removeNode(ListNode* head,int n){
  // TODO: 填写删除链表中指定值的函数
}

本题的其他定义 (你不需要参与修改的部分，也不需要提交它) 为:

#include "stdio.h"
#include "stdlib.h"

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *createList(int a[], int n);

struct ListNode *sortList(struct ListNode *head);

void output(struct ListNode *head);

struct ListNode *insertNode(struct ListNode *head, int n);

struct ListNode *removeNode(struct ListNode *head, int n);

int main() {
    int a[10000];
    int n, ins, rm;
    scanf("%d", &n);
    scanf("%d", &ins);
    scanf("%d", &rm);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    struct ListNode *list = createList(a, n);
    output(list);
    list = sortList(list);
    output(list);
    list = insertNode(list, ins);
    output(list);
    list = removeNode(list, rm);
    output(list);
    return 0;
}

ps：在删除中可能会删除不存在的元素

完整答案代码

struct ListNode* createList(int a[],int n){
	struct ListNode *preNode=NULL;
	struct ListNode *head=NULL;
	for(int i=0;i<n;i++){
		struct ListNode *newNode=(struct ListNode*)malloc(sizeof(struct ListNode));
		if(newNode==NULL)return head;
		newNode->val=a[i];
		newNode->next=NULL;
		if(i==0){
			head=newNode;
		}else{
			preNode->next=newNode;
		}
		preNode=newNode;
	} 
	return head;
}
struct ListNode* sortList(struct ListNode* head){
	struct ListNode *p=head;
	struct ListNode *q=head;
	for(;p!=NULL;){
		q=p->next;
		for(;q!=NULL;){
			if((p->val)>(q->val)){
				int t=(p->val);
				p->val=q->val;
				q->val=t;
			}
			q=q->next;
		}
		p=p->next;
	}
	return head;
}
void output(struct ListNode *head){
	struct ListNode *p=head;
	while(p!=NULL){
		printf("%d\n",p->val);
		p=p->next;
	}
}
struct ListNode* insertNode(struct ListNode* head,int n){
	struct ListNode *prev=head,*pNext=head;
	struct ListNode *newNode=(struct ListNode*)malloc(sizeof(struct ListNode));
	newNode->val=n;
	newNode->next=NULL;
	while((pNext!=NULL)&&(pNext->val<n)){
		prev=pNext;
		pNext=pNext->next;
	}
	if(pNext==head){
		newNode->next=pNext;
		head=newNode;
	}else{
		prev->next=newNode;
		newNode->next=pNext;
	}
	return head;
}
struct ListNode* removeNode(struct ListNode* head,int n){
	struct ListNode *prev=head,*pNext=head;
	while(pNext!=NULL&&pNext->val!=n){
		prev=pNext;
		pNext=pNext->next;
	}
	if(pNext==NULL){
		return head;
	}else if(pNext==head){
		head=pNext->next;
		free(pNext);
	}else{
		prev->next=pNext->next;
		free(pNext);
	}
	return head;
}

如能打赏，不胜感激[叩谢]。

标签：11,head,12,ListNode,struct,int,链表,山东大学,pNext
From： https://blog.csdn.net/Water_Star1/article/details/141319634

山东大学计算机导论与程序设计基础实验11-12

A : 实验11 斐波那契序列

题目描述

输入格式

输出格式

完整答案代码

B : 实验11 递归折半查找

题目描述

输入格式

输出格式

完整答案代码

C : 实验11 递归寻找最大值

题目描述

输入格式

输出格式

完整答案代码

D : 实验11 递归寻找假币

题目描述

输入格式

输出格式

完整答案代码

E : 实验12 贪心

题目描述

输入格式

输出格式

完整答案代码

F : 实验12 链表相关操作

题目描述

输入格式

输出格式

Hint

完整答案代码

相关文章

赞助商

阅读排行