首页 > 编程语言 >山东大学计算机导论与程序设计基础实验11-12

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

时间:2024-08-19 10:55:51浏览次数:8  
标签: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

相关文章

  • 合宙Air780E开发板集成EC11旋转编码器实战指南
    合宙Air780E开发板,作为一款基于Cat.1技术的物联网通信模组开发板,依托移芯EC618平台,以其低功耗、全网通及丰富的接口支持特性,它支持AT指令和LuatOS二次开发,在物联网领域展现出了强大的竞争力。今天我们来讲解一个基于Air780E开发板,集成ec11旋转编码器的实例。 合宙支持LuatO......
  • 意得辑真不错,85喆优惠码延长到25.12.31了我用editage意得辑润色SCI已经第4年了,今天他
    意得辑真不错,85喆优惠码延长到25.12.31了我用editage意得辑润色SCI已经第4年了,今天他家的学术支持老师让我写几句感受,那我真的感受太多了。因为下单太多一度被导师怀疑是在他家套经费。22年刚读博同时润色了三篇,被导师叫到办公室,问我是什么途径联系到的。我说师兄给说的,网上下......
  • 智汇API推出新套餐:免费版 Mistral Large 2407 123B 扩展包
    “免费版(MistralLarge2407123B扩展包)”是英智大模型推理API服务平台面向开发者推出的MistralLarge2407123B免费套餐,供广大开发者无门槛、不限制Tokens、永久使用,每位用户限购1次。包含服务:“英智MistralLarge2407123B服务”:QPS(每秒查询数)限制为1次,统计To......
  • Oracle 12c后enable_ddl_logging的日志位置变化
     Oracle12c后enable_ddl_logging的日志位置变化 先吐个槽,enable_ddl_logging功能是OracleChangeManagementPack的一部分,需要作为单独的许可证购买,要单独花钱......开启enable_ddl_logging功能,在11g中,ddl操作将以XML格式被记录在ADR_HOME/trade/alert_<SID>.log文件中......
  • GitHub每周最火火火项目(8.12-8.18)
    项目名称:goauthentik/authentik项目介绍:authentik是一个认证中间件,它提供了强大的认证和授权功能,可以满足各种复杂的业务需求。它支持多种认证方式,如用户名/密码、OAuth2、OpenIDConnect等,并可以与各种应用程序和系统集成。authentik还提供了友好的用户界面和管理工......
  • 12-CEF快速转发1
    思科的转发方式1.process2.fastswitch3.cefcam和tcam表内存可寻址存储器(cam)是一种专用于进行查表操作的硬件芯片cam工作在二进制情况下0/1tcam工作在三进制情况下0/1/x这两者都是多层交换的硬件组件,另通常还包括asic(application-specificintegratedcircuit应用专用......
  • Python学习笔记 DAY11
    字符串查找count(sub[,start[,end]])find(sub[,start[,end]])rfind(sub[,start[,end]])index(sub[,start[,end]])rindex(sub[,start[,end]])x="上海自来水来自海上"x.count("海")2x.count("海",0,5)1x.find("海")1x.rfind("海&q......
  • Win7/Win10/Win11开启本地内核调试的方法
    具体内容微软官方文档上都有:https://learn.microsoft.com/zh-cn/windows-hardware/drivers/debugger/performing-local-kernel-debugginghttps://learn.microsoft.com/zh-cn/windows-hardware/drivers/debugger/setting-up-local-kernel-debugging-of-a-single-computer-manually......
  • 代码随想录算法训练营第11天|二叉树part01
    理论基础需要了解二叉树的种类,存储方式,遍历方式以及二叉树的定义二叉树纯理论方面还是比较简单,以前都学过,没什么可讲的。满二叉树就是满了,完全二叉树就是层满了(而且是左边)。平衡二叉搜索树就是左右深度绝对值差1。一般采用链式存储方式,顺序存储结构如果父节点的数组......
  • 诗|随想——202311-12月的一些絮絮叨叨
    诗|随想——202311-12月的一些絮絮叨叨20231122随想01茫然随想02平和20231122随想03活着随想04爱随想05呓语20231123随想06失去随想07朦胧随想08成长随想09爱你20231124随想10掌控随想11秘密随想12我记得20231125随想13你我随想14祈盼随想15生命......