首页 > 其他分享 >山东大学数据结构实验一(1)

山东大学数据结构实验一(1)

时间:2023-04-25 20:11:37浏览次数:44  
标签:int sum 元素 异或 num 实验 子集 数据结构 山东大学

题目描述

现有一个有\(n\)个元素的序列\(a=[a_1,a_2,\cdots, a_n]\),定义这个序列的价值为\(\sum_{i=1}^{n}i\times a_i\)。空序列的价值为\(0\)。

先给你一个长度为\(n\)的序列\(a\),求\(a\)中所有子集价值的异或和,要求子集中元素的相对位置保持不变。

异或和: 位运算的一种。如果a、b两个值不相同,则异或结果为\(1\);如果a、b两个值相同,异或结果为\(0\)。

输入输出格式

输入

第一行一个整数\(n\)

接下来一行有n个非负整数表示\(a_1, a_2, \cdots, a_n\)

输出

一个整数表示所有子集的异或和

样例1

输入

2
1 2

输出

6

数据规模

\(1\leq n\leq20\),\(1\leq a\leq10^5\)

提示

样例1中共有四个子集\([],[1],[2],[1,2]\),他们的价值分别为0,1,2,5,其异或和\(0\bigoplus1\bigoplus2\bigoplus5=6\)

/* created by LYZ */
#include<iostream>
using namespace std;

int *stor=new int[100];//用于存储选中的元素
int * flag = new int[20];//用于记录当前元素选或者不选

int value = 0;
int searchValue(int* array, int a, int b){
	int sum = 0; 
	int num=0;
	if (a < b){
		flag[a] = 0;//不选择当前元素进入子集
		searchValue(array,a + 1, b);//对下一个元素进行选择
		flag[a] = 1;//选择当前元素进入子集
		searchValue(array,a + 1, b);//对下一个元素进行选择
	}
	if (a == b)//当a==b时选择结束,统计选中的值进入到数组stor中
	{

		for (int i = 0; i < a; i++)
		{
			if (flag[i] == 1){ stor[num] = array[i]; num++; }
		}
		for (int i = 0; i < num; i++){
			sum += stor[i] * (1 + i);//计算总价值
		}
		value ^= sum;//计算异或和
	}
	
	return value;

}

int main(){
	int n;
	cin >> n;
	int *a = new int[20];
	for (int i = 0; i < n; i++)
		cin >> a[i];//输入数组中每个元素的值
	cout << searchValue(a, 0, n) << endl;
	delete []a;
	delete[]stor;
	delete[]flag;
	return 0;

}

标签:int,sum,元素,异或,num,实验,子集,数据结构,山东大学
From: https://www.cnblogs.com/lyz103/p/17353703.html

相关文章

  • 实验三
    任务一实验源码运行结果截图任务二实验源码1lst=[55,92,88,79,96]23i=04whilei<len(lst):5print(lst[i],end='')6i+=17print()89foriinrange(len(lst)):10print(lst[i],end='')11print()1213forii......
  • 实验3 控制语句与组合数据类型应用编程
    实验任务1实验源码1importrandom23print('用列表存储随机整数:')4lst=[random.randint(0,100)foriinrange(5)]5print(lst)67print('\n用集合存储随机整数:')8s1={random.randint(0,100)foriinrange(5)}9print(s1)1011print('......
  • 实验3
    1.实验任务1task1.py实验代码:importrandomprint('用列表储存随机整数:')lst=[random.randint(0,100)foriinrange(5)]print(lst)print('\n用集合储存随机整数:')s1={random.randint(0,100)foriinrange(5)}print(s1)print('\n用集合储存随机整数:')s......
  • 实验3
    实验任务1:源码:importrandomprint('用列表存储随机整数:')lst=[random.randint(0,100)foriinrange(5)]print(lst)print('\n用集合存储随机整数:')s1={random.randint(0,100)foriinrange(5)}print(s1)print('\n用集合存储随机整数:')s2=set(......
  • 实验三
    实验任务一:实验源码:1importrandom23print('用列表存储随机整数:')4lst=[random.randint(0,100)foriinrange(5)]5print(lst)67print('\n用集合存储随机整数:')8s1={random.randint(0,100)foriinrange(5)}9print(s1)1011print('\......
  • 实验三
    task1源代码importrandomprint('用列表存储随机整数:')lst=[random.randint(0,100)foriinrange(5)]print(lst)print('\n用集合存储随机整数:')s1={random.randint(0,100)foriinrange(5)}print(s1)print('\n用集合存储随机整数:')s2=set()whilelen(......
  • 实验3 控制语句与组合数据类型应用编程
    一.实验目的:1.知道Python中组合数据类型字符串(str)、列表(list)、元组(tuple)、集合(set)、字典的表示、特性2.能够正确、熟练使用字符串(str)、列表(list)、元组(tuple)、集合(set)、字典的常用操作3.针对具体问题场景,能够灵活、组合使用多种数据类型,应用或设计算法,使用......
  • 实验3
    实验任务1源代码:importrandomprint('用列表存储随机整数:')lst=[random.randint(0,100)foriinrange(5)]print(lst)print('\n用集合存储随机整数:')s1={random.randint(0,100)foriinrange(5)}print(s1)print('\n用集合存储随机整数:')s2=set()whil......
  • linux操作系统分析实验五-深入理解进程切换
    Lab5:深入理解进程切换首先找到对应进程调度的代码文件Kernal/sched/core.c  找到context_switch()函数   其中包括rq,为进程的runningqueue;以及进程切换前后的进程描述符prev和next  首先调用一些函数做上下文切换的准备,与最后出现的finish_task_switch()成......
  • 数据结构(刷题)
                  ......