题目：
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行为一个整数，即该整数有多少种因子分解方法。其后有若干行，分别表示该整数的分解方法。其形式如下：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)

距离算法考试还有两周的时间，准备从现在开始用笔记的形式记录自己学习或复习算法课程的成果。不是有那么一句名言嘛：好记性不如烂笔头。Learn From Now!
算法是一系列解决问题的清晰指令，即对符合一定规范的输入，在有限时间内获得所要求的输出。


算法需要满足以下四大性质：
1、输入：有零个或多个外部量作为算法的输入（意思是可以没有输入）
2：输出：有一个或多个量作为输出（意思是必须有输出）
3、确定性：组成算法的每条指令清晰，无歧义。
4、有限性：算法中每条指令的执行次数或执行时间在有限的范围内。
在这里特别强调与程序的区别：
程序是算法用某种程序设计语言的具体实现。（可不满足以上四大性质）
以下是算法的几个要点：
1、算法的每个步棸都必须清晰，明确，不得有半点模糊。
2、算法所处理的值域必须仔细定义。
3、同样一种算法可以用不同的形式描述
4、同一个问题可能存在不同的解决算法
5、针对同一个问题不仅可能解决算法的思路差别很大，而且解题速度可能也会相差很大。
算法概念的再理解：
算法是问题的程序化解决方案，这些解决方案本身并不是答案，而是能够得到答案的精准指令。
名言：人们常说，一个人只有把知识教给别人，才能真正掌握它。实际上，一个人只有把知识教给“计算机”，才能真正掌握它。
算法中的所有理解性的概念中最难的当数复杂度分析了：时间复杂度、空间复杂度
算法复杂度分析是指算法在运行过程中所需的计算机资源量。
需要的时间资源的量叫时间复杂度；
需要的空间资源的量叫空间复杂度。


用T和S来表示时间复杂性和空间复杂性，有： 

T=T(N,I)和S=S(N,I)。 
N代表问题的规模，I代表输入。


假定计算机上能够提供k种元运算，记为：O1，O2，…,Ok，
执行一次这些元运算所需要的时间分别为  t1，t2，…,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);
    }
}