精华内容
下载资源
问答
  • 设计个算法,将它找出来;要求:不用辅助存储空间。 首先介绍异或运算 异或运算:又称不进位加法(是二进制所进行操作) (1+1=0; 0+0=0; 1+0=1) 性质: 1、交换律 可任意交换运算因子位置,结果不变 2...

    题目:

    1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个
    元素重复,其他均只出现一次。 每个数组元素只能访问一次
    设计一个算法,将它找出来;要求:不用辅助存储空间。

    • 首先介绍异或运算
    • 异或运算:又称不进位加法(是对二进制所进行的操作)
      (1+1=0; 0+0=0; 1+0=1)
    • 性质:
      1、交换律 可任意交换运算因子的位置,结果不变
      2、结合律:即(a ^ b)^ c = a ^ (b ^ c)
      3、对于任何数x,都有x ^ x=0, x ^ 0=x,同自己求异或为0,同 0求异或为自己
      4、自反性 A ^ B ^ B = A ^ 0 = A

    Java实现

    package Demo1.Demo1_4;
    
    import java.util.Random;
    
    public class Demo1_4_main {
        public static void main(String[] args) {
            int N = 11;
            int [] arr = new int[N];
            for(int i = 0; i < arr.length-1 ;i++) {
                arr[i] = i+1;
            }
            //最后一个数为随机数
            arr[arr.length-1] = new Random().nextInt(N-1)+1;
            print(arr);
            //  交换重复数字与随机位置处数字的位置
            swap(arr,arr.length-1,new Random().nextInt(N));
            print(arr);
    
            // 定义一个 x = 0, x^任意数 = 任意数
            int x = 0;
            for(int i = 1; i <= N-1; i++){
                x = x^i;
            }
            for(int i = 0; i < arr.length;i++){
                x = x^arr[i];
            }
            System.out.println("重复数字:" + x);
        }
        public static void print(int arr[]){
            for(int i = 0; i < arr.length; i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }
        public static void swap(int arr [], int p,int q){
            int temp = arr[p];
            arr[p] = arr[q];
            arr[q] = temp;
        }
    }
    
    

    C++实现

    其中生成随机数可参考算法学习(三)

    #include <iostream> 
    #include <cstdlib>	//	导入 srand() 和 rand() 
    #include <ctime>
    using namespace std;  
    
    void swap(int *arr,int p,int q){	//	定义一个函数用于交换数组中数的位置 
    	int temp = arr[p];
    	arr[p] = arr[q];
    	arr[q] = temp;
    }
    
    void print(int *arr,int n) {				//	定义一个函数用于输出数组 
    	for(int i = 0; i < n; i++){
    		cout<<arr[i]<<'\t'; 
    	}
    	cout<<endl;
    }
    int main() 
    {
    	srand(time(0));	//	设置一个随机种子 
    	int n;
    	cout<<"请输入数组长度:"<<endl;
    	cin>>n;			//	输入1001 
    	int *arr = new int [n];
    	for(int i = 0; i < (n-1); i++)
    		arr[i] = i+1;
    	arr[n-1] = rand()%(n-1)+1;	//	产生 [1,1000]中随机数 
    	print(arr,n);
    	swap(arr,n-1,rand()%n);	//	随机生成[0,n-1]的随机数,交换重复的数与随机位置处数的位置 
    	cout<<endl;
    	print(arr,n);
    	
    	int x=0;
    	for(int i = 0; i<n-1; i++){
    		x = x^(i+1);		// x = 1^2^3^4……^n-1
    	}
    	for(int i = 0; i<n; i++){
    		x = x^arr[i];		// x = 1^1^2^2^……^n^n^重复的那个数 
    		//	x = 重复的数; 
    	}
    	cout<<"重复的数为:"<<x<<endl; 
    	system("pause");
    	return 0;
    }
    

    在这里定义的是一个指针类型,大家如果自己写代码的时候可能会用 int arr [ n]来定义数组,此时如果定义print的时候可能会遇到一个数组传参的问题,对于数组的length我们可以通过sizeof(arr)/sizeof(arr[0])来求得,但是在数组作为函数的实参传递时,传递的是数组的第一个元素地址,大小仅仅为一个指针类型的大小。可参考文章C++数组作为函数参数的几个问题
    当我们想要在自己定义的函数里使用数组的长度时可以这么定义函数:

    void print(int arr [], int arrlength){balabala}
    

    然后在main中调用时:

    print (arr,  sizeof(arr)/sizeof(arr[0]);
    

    这篇是我在算法学习中遇到的问题以及学习笔记!欢迎大家评论区进行指导!

    展开全文
  • 给定一整数n,其进行因子分解,编写程序,求解所有分解方法,并统计其有多少种不同分解方法。 输入要求: 输入整数n,占1行。 输出要求: 输出第1行为一整数,即该整数有多少种因子分解方法。其后有若干...

    题目重述

    给定一个整数n,对其进行因子分解,编写程序,求解所有的分解方法,并统计其有多少种不同的分解方法。
    输入要求: 输入整数n,占1行。
    输出要求:
    输出的第1行为一个整数,即该整数有多少种因子分解方法。其后有若干行,分别表示该整数的分解方法。其形式如下:6=2 * 3
    样例输入:12
    样例输出:
    8
    12=2 * 2 * 3
    12=2 * 3 * 2
    12=2 * 6
    12=3 * 2 * 2
    12=3 * 4
    12=4 * 3
    12=6 * 2
    12=12

    题目分析

    对一个整数进行因子分解,实际生就是寻找对这个整数求模等于0的整数,运用模运算此整数可被分为两个整数, 然后再对这两个整数进行因子分解。也就是说,解决因子的因子分解,直到分解出的因子不可再分。
    为了使因子分解具有一定顺序,我们可以采用树的结构来对理解算法:
    在这里插入图片描述
    本文将利用整形数组实现以上功能。

    算法的流程

    Step1:定义一个等于0的整形空数组s;
    Step2:输入这个整数n,将s[0]赋值为n;
    Step3:计从i=2开始至i=n,若这个整数n能被i整除,将这个整数分为两个整数i和n’(n’=n/i),若n不等于i,则对n’重复Step2,否则,num++,函数返回;
    Step4:输出有多少种分法num;
    Step5:从i=2开始至i=n,若这个整数n能被i整除,将这个整数分为两个整数i和n’(n’=n/i),因子i赋值给s[k],k++,若n不等于i,则对n’重复Step5,否则k–,进入Step6,函数返回;
    Step6:输出s[0]和“=”,继续以格式“s[i]*”输出s[1]至s[k-1],最后输出s[k];

    程序设计

    #include<iostream>
    using namespace std;
    void figure(int n,int &m) {
     for (int i = 2; i <= n; i++)//从2开始分解
     {
      if (n % i == 0)//i是n的因子
      {
       if (n != i)
       {
        figure(n / i, m);//对其中一个整数再进行分解
       }
       else//当不可再分时,便是函数的出口,返回上一级
       {
        m++;
        return;
       }
      }
     }
    }
    void push(int* s,int &k) {
     int i = 0;
     for (i = 0;i<=k-1; i++) {
      if (i == 0)
       cout << s[i] << "=";
      else
       cout << s[i]<<"*";
     }
     cout << s[k] << endl;
    }
    /********************/
    //此函数的结构与figure函数相似,但每一步会进行一次输出
    void distine(int n,int k,int* s) {
     for (int i = 2; i <= n; i++)
     {
      if (n % i == 0) {
       s[k++] = i;
                 if (n!=i)
           {
                    distine(n / i,k,s); 
        k--;
            }
          else
           {
           push(s, --k);//输出每种分解方法
            return;
           }
      }
      
     }
    }
    void main() {
     int n = 0, num = 0;
     int s[100] = {0,0,};//约束这个整数最多有99个因子
     /*********************/
     cin >> n;//输入这个整数
     s[0] = n;//数组的0号单元存储这个数
     /********************/
        figure(n,num);//统计有多少种分解方法
     cout << num<<endl;
     /********************/
     distine(n,1,s);
    }
    

    算法的时间复杂度分析

    算法最差时间复杂度:T(n)=4*(n/2)log2n+……=o((n/2)log2n
    算法最差时间复杂度:T(n)=2*n+2=o(n)

    展开全文
  • 算法是一系列解决问题清晰指令,即符合一定规范输入,在有限时间内获得所要求的输出。 算法需要满足以下四大性质: 1、输入:有零或多外部量作为算法的输入(意思是可以没有输入) 2:输出:有一或多...

    距离算法考试还有两周的时间,准备从现在开始用笔记的形式记录自己学习或复习算法课程的成果。不是有那么一句名言嘛:好记性不如烂笔头。Learn From Now!

    算法是一系列解决问题的清晰指令,即对符合一定规范的输入,在有限时间内获得所要求的输出。


    算法需要满足以下四大性质

    1、输入:有零个或多个外部量作为算法的输入(意思是可以没有输入)

    2:输出:有一个或多个量作为输出(意思是必须有输出)

    3、确定性:组成算法的每条指令清晰,无歧义。

    4、有限性:算法中每条指令的执行次数或执行时间在有限的范围内。

    在这里特别强调与程序的区别:

    程序是算法用某种程序设计语言的具体实现。(可不满足以上四大性质)

    以下是算法的几个要点:

    1、算法的每个步棸都必须清晰,明确,不得有半点模糊。

    2、算法所处理的值域必须仔细定义。

    3、同样一种算法可以用不同的形式描述

    4、同一个问题可能存在不同的解决算法

    5、针对同一个问题不仅可能解决算法的思路差别很大,而且解题速度可能也会相差很大。

    算法概念的再理解:

    算法是问题的程序化解决方案,这些解决方案本身并不是答案,而是能够得到答案的精准指令。

    名言:人们常说,一个人只有把知识教给别人,才能真正掌握它。实际上,一个人只有把知识教给“计算机”,才能真正掌握它。

    算法中的所有理解性的概念中最难的当数复杂度分析了:时间复杂度、空间复杂度

    算法复杂度分析是指算法在运行过程中所需的计算机资源量。

    需要的时间资源的量叫时间复杂度;

    需要的空间资源的量叫空间复杂度。

    TS来表示时间复杂性和空间复杂性,有: 

    T=T(N,I)S=S(N,I)。 

    N代表问题的规模,I代表输入。

    假定计算机上能够提供k种元运算,记为:O1O2…,Ok

    执行一次这些元运算所需要的时间分别为  t1t2…,tk

    对于给定算法A,所用到的,Oi的运算次数为ei,i=1,2,…,k,

    因为ei 是N,I的函数,即:ei= ei(N,I)。

    因此:

          

    算法的时间的复杂度可从以下三个方面进行分析:

    1、最坏情况下的时间复杂度

    2、最好情况下的时间复杂度

    3、平均情况下的时间复杂度

    一般情况下,我们研究算法是研究其最坏情况下的时间复杂度。最好情况下的时间复杂度是在特例情况下发生的,不具有代表性。如果能保证最坏情况下的效率是理想的,对于问题的解决才是有意义的。

    非递归算法一般从以下四个方面来分析:
    (1)for/ while 循环
    循环体内计算时间*循环次数;
    (2)嵌套循环
    循环体内计算时间*所有循环次数;
    (3)顺序语句
    各语句计算时间相加;
    (4)if-else语句
    if语句计算时间和else语句计算时间的较大者。
    例如:(插入排序算法)

    template<classType>

    voidinsertion_sort(Type *a, intn)

    {

        Type key;                                      //   cost        times

        for (int i = 1; i< n; i++){                 //    c1          n  

              key=a[i];                                  //    c2          n-1

              int j=i-1;                                   //    c3          n-1

              while( j>=0 && a[j]>key){       //    c4          sum of ti

       a[j+1]=a[j];                          //    c5          sum of (ti-1) 

       j--;                                       //    c6          sum of (ti-1)

       }

             a[j+1]=key;                              //    c7          n-1

            }

    }

    最坏情况下时间复杂度为:O(n*ti)

    最好情况下时间复杂度为:O(n)#这是在原来排好序的情况下

    因此时间复杂度:O(n的平方)

    本文为算法复习第一篇,也是算法迅速提升的开始。不足之处,日后改之。

    展开全文
  • 首先该问题必须满足下列四个要求: 读者可以共享 写者互斥 除非有一个写者在访问共享数据集,其他情况下,读者不等待 写者执行写操作前,应该让所有读者和写者退出 对于写者来说,只要设置一个写者与写者...

    首先该问题必须满足下列四个要求:

    读者可以共享

    写者互斥

    除非有一个写者在访问共享数据集,其他情况下,读者不等待

    写者执行写操作前,应该让所有读者和写者退出


    对于写者来说,只要设置一个写者与写者之间、读者与写者之间共享的一个信号量w即可,w=1;对于读者,需要特殊处理,要求对读者进行计数,因为,读者对文件是共享的,对于第一个读者,需要对数据集“加锁”,防止写者对数据集进行访问,而其他读者可以直接进入访问数据集;对于最后一个读者,需要“解锁”,以便让写者或后面的读者能够访问数据集。读者计数ReadCnt,与之互斥的信号量mutex,初值为0。

    程序如下:

    typedef int Semaphore
    Semaphore mutex = 1, w = 1;
    int ReadCnt = 0;
    //下面读者与写者进程并发执行
    process Reader(void)
    {
        while(1)
        {
            P(mutex);
            ReadCnt++;
            if(1 == ReadCnt)
            P(w);
            V(mutex);
            /*对数据集进行读操作*/
            P(mutex);
            ReadCnt--;
            if(0 == ReadCnt)
                V(w);
            V(mutex);
        }
    }
    process Writer(void)
    {
        while(1)
        {
            P(w);
            /*对数据集进行写操作*/
            V(w);
        }
    }

    展开全文
  • 如果两不同正整数,他们和是他们因子,就被成为兄弟数 小是弟数,大是兄数。 先后输入正整数 n 和 m (n < m),请在 n 至 m-n+1 数中,找出一对 兄弟数。如果找不到就输出 No,找得到就和最小...
  • 要求编写程序并进行测试,该程序可每一次资源申请采用银行家算法进行分配。 【课题内容】 (1)设计资源(≥3); (2)设计进程(≥3); (3)设计银行家算法相关数据结构; (4)动态进行资源申请、...
  • C语言求两数最大公约数的四算法

    千次阅读 2019-03-12 20:07:28
    2.通过问题分析,设计合理的算法解决问题。 实验内容 运行最大公约数常用算法,并进行程序调式与测试,要求程序设计风格良好,并添加异常处理模块(如输入非法等)。 题目分析 求两数最大公约数,常用...
  • 1. 算法步骤将待排序N数依次进行相邻两比较,如果不符合由小到大顺序要求(即前小后大),则交换两位置,否则不交换。待N数经过N-1次相邻两数比较后,最大数就交换到了最后位置,这数就算排...
  • 2、Object作为HashMapkey话,Object有什么要求吗? 3、一致性哈希算法 4、什么是hashmap? 5、Java中HashMap工作原理是什么? 6、hashCode()和equals()方法重要性体现在什么地方? ❤2、树 1、说一下B+树...
  • 通过问题分析,设计合理的算法解决问题; 二. 实验内容 运行最大公约数常用算法,并进行程序调式与测试,要求程序设计风格良好,并添加异常处理模块(如输入非法等)。 三. 算法及流程图 1.辗转相除法 ...
  • 实验 银行家算法的实现 1实验目的 通过编写和调试银行家算法的模拟程序以加深避免死锁方案理解 熟悉银行家算法的分 配思想 2 实验要求 设计银行家方案并编写模拟程序实现之已知系统总共资源数进程名 ...
  • 利用随机函数产生N随机整数(20000以上),这些数进行多种方法进行排序。 要求: 1) 至少采用三种方法实现上述问题求解(提示,可采用方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并...
  • word范文 实验 磁盘调度 一实验目的 本实验要求学生模拟设计磁盘调度程序观察调度程序动态运行过程通过实验让学生理解和掌握磁盘调度职能 二实验内容 磁盘进行移臂操作模拟磁盘调度算法并计算平均寻道...
  • 四色猜想:四色问题是m图着色问题特例,根据四色原理,证明平面或球面上任何地图所有区域都至多可用种、颜色来着色,并使任何两有一段公共边界相邻区域没有相同颜色。这问题可转换成一平面图...
  • 操作系统实验 磁盘调度算法 PAGE PAGE 1 实验 磁盘调度 一实验目的 本实验要求学生模拟设计磁盘调度程序观察调度程序动态运行过程通过实验让学生理解和掌握磁盘调度职能 二实验内容 磁盘进行移臂操作...
  • 银行家算法的实现.pdf

    2020-07-29 06:41:51
    实验 银行家算法的实现 1实验目的 通过编写和调试银行家算法的模拟程序以加深避免死锁方案 理解熟悉银行家算法的分配思想 2 实验要求 设计银行家方案并编写模拟程序实现之已知系统总共 资源数进程名进程...
  • 算法何为

    2020-09-20 23:12:10
    一、算法 算法(algorithm)是特定问题求解步骤的一种描述,它是指令的有限...算法设计的要求 正确性、可读性、健壮性、高效率与低存储量的需求 五、算法效率的度量 时间复杂度(渐进时间复杂度) T(n)=O
  • 其实从能用性角度上来看,不分代也能满足我们的要求,但是这边就会出现一很严重问题,如果堆内存不分代话,那么我们所有对象都被放在了同一块内存空间中,这样做gc回收垃圾时候,我们就需要堆所有...
  • 8.1.2 面向对象程序设计的特点 8.1.3 类和对象的作用 8.1.4 面向对象的软件开发 8.2 类的声明和对象的定义 8.2.1 类和对象的关系 8.2.2 声明类类型 8.2.3 定义对象的方法 8.2.4 类和结构体类型的异同 8.3 类的成员...
  • 数据结构算法

    2020-04-28 20:03:39
    1、算法设计的好坏关乎程序的执行效率,算法的设计必须满足下列四个要求。 正确性:正确性的含义是算法对于一切合法的输入数据都能够得出满足要求的结果,事实上要验证算法的正确性是极为困难的,因为通常情况下...
  • 在排序算法面试中,面试官喜欢考察就是插入排序、冒泡排序、归并排序、快速排序这种排序算法,其中快速排序一般会要求现场写代码,这要注意一下。 这些算法考察点就是要对算法的特点烂熟于胸,熟悉它们...
  •  上几篇说都是根据要求输出一些字符、图案等,今天就再说一“上三角”,有点类似于第二篇说正螺旋,输出字符少了,但是逻辑稍微复杂了点。 程序描述  方阵角线之上称为“上三角”。 请你设计...
  • 其次,我们分析了计算算法的四个主要计算模块。 第三,设计了多线程并行算法和MPI并行化。 最后,实现了多线程并行和MPI并行。 实验结果表明,多线程并行和MPI并行化算法可以大大提高整体计算效率。 并且,MPI...
  • 但是,要想设计优秀哈希算法并不容易,根据我经验,我总结了需要满足几点要求: 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 输入数据非常敏感,哪怕原始数据只修改了一 Bi
  • (2)用银行家算法设计一个资源分配程序,运行这两个程序,观察系统运行情况,并系统运行每一步情况进行显示。 具体做法: 1.首先建立一个数组类,包含四个元素(即代表四个进程),在类中定义四个私有变量need,...
  • 在实验,我们学习了checked Exception,实验要求我们利用checked ExceptionApp进行改造,我想tmd这不是叫我重构那三烂代码吗?思考了小久,我突然觉得我App里很多东西是多余,那些杂糅的算法完全可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 513
精华内容 205
关键字:

对算法设计的四个要求