简介

==============================================================================================================



一、局部对象

在C++中，每个名字都有作用域，而每个对象都有生命期；
名字的作用域指的是知道该名字的程序文本区（哪些地方可以用）；
对象的生命期则是在程序执行过程中对象存在的时间（什么时候可以用，什么时候不可以了）；
在函数中定义的形参和变量的名字只位于函数的作用域中，这些名字只在函数体中可见，通常，变量名从声明或定义的地方开始到包围它的作用域结束处都是可用的。
1、自动对象

默认情况下，局部变量的生命期局限于所在的函数的每次执行期间。
只有当定义它的函数被调用时才存在的对象称为自动对象
自动对象在每次调用函数时创建和撤销。 
局部变量所对应的自动对象在函数控制经过变量定义语句时创建。
如果在定义时提供了初始化式，那么每次创建对象时，对象都会被赋予指定的初值。
对于未初始化的内置类型局部变量（局部变量不会默认初始化的，全局变量就会），其初值不确定，函数调用结束时，自动对象就会被撤销。
形参也是自动对象，形参所占用的存储空间在调用函数时创建，在函数结束时撤销。当函数结束时，会释放它的局部存储空间，而且，在函数结束后，自动对象和形参的值都不能再访问 了；
 - 
2、静态局部对象

一个变量如果位于函数的作用域内，但生命期却跨越了这个函数的多次调用，这种变量很有用 ，往往定义为static（静态的）；
static局部对象确保不迟于在程序执行流程第一次经过该对象的定义语句时进行初始化，这种对象一旦被创建，在程序结束前都不会撤销。
当定义静态局部对象的函数结束时，静态局部对象不会撤销。在该函数被多次调用的过程中，静态局部对象会持续存在并保持它的值。
size_t count_calls(){
    static size_t ctr=0;//定义一个静态的局部的变量，而且该变量已经被初始化
    return ++ctr;
}

int main(){
  for(size_t i=0;i!=10;i++)
  cout<<count_calls()<<endl;//依次输出1--10
  return 0;
}
//在第一次调用函数count_calls之前，ctr就已经创建并赋予初值0.每次函数调用都使ctr加1，并且返回其当前值。在执行函数count_calls时，变量ctr就已经存在并且保留上次调用该函数时的值，因此第二次调用时，ctr的值为1，第三次为2.。
//如果去掉static ，那么结果就是10个1.因为每次调用结束ctr就被撤销了，再次调用的时候又重新建立并初始化。



习题 7.27 （important）

解释形参、局部变量和静态局部变量的差别。并给出一个有效使用了这三种变量的程序例子。

从本质上讲，三者均属于局部作用域中的变量，其中，局部变量又分为普通（非静态）和静态局部变量。



1、 形参的作用域为整个函数体，而普通（非静态）局部变量和静态局部变量的作用域为：从定义处到包含该变量定义的块的结束处；



2、形参由调用函数时所传递的实参初始化；而普通（非静态）局部变量和静态局部变量通常用初始化式进行初始化，且均在程序执行流程第一次经过该对象的定义语句时进行初始化。静态局部变量的初始化在整个程序执行过程中只进行一次；



3、形参和普通（非静态）局部变量均属于自动变量，在每次调用函数时创建，并在函数结束时撤销：而静态局部变量的生命期却跨越了函数的多次调用，它在创建后直到程序结束时才撤销。(一个是函数结束时撤销，一个是程序结束时撤销)

int fac(int x){
  static int result=1;
  result*=x;
  return result;
}
int main(){
  int upmut;
  cout<<"please input :"<<endl;
  cin>>upmut;
  for(int i=1;i<=upmut;i++){
  cout<<fac(i)<<endl;//依次输出从1到upmut之间所有整数的阶乘
  }
  return 0;
}



int k;//全局变量，未初始化，默认初始化未0
int main(){
  static int i;    //静态局部变量i ，未初始化，默认初始化未0
  int j;           //局部变量，不会默认初始化
  cout<<k<<endl;   //输出 0
  cout<<i<<endl;   //输出 0
  cout<<j<<endl;   //未初始化
  return 0;
}

是什么

效应局部化中的“效应“是指修改带来的影响。

效应局部化是指修改带来的影响控制在局部。

效应局部化是一个很重要的原则。围绕该原则产生了许多技术，模块化就是其中之一。模块化技术的目标之一就是让修改模块所带来的影响停留在该模块的内部。

为什么

在效应非局部化的情况下，某处修改会对其他完全不相关的地方造成影响，使修改成本大幅增加。

这是如果我们知道哪些地方受到影响，或许还有救。然而在大部分情况下，我们对此是一无所知，这时就得先花时间排查影响范围。、

但在效应局部化的情况下，我们需要阅读代码以及修改所带来的影响都会限制在一定的范围内。

另外， 效应局部化还有让交流更加顺畅的效果，在效应局部化的情况下， 程序员只要理解当前阶段所涉及的代码即可，不需要一次性掌握所有的代码。

怎么做

在编写代码时，要让关系紧密的代码集中在一起，同时保证关联性较弱的代码不互相依赖，为此，我们需要将关系紧密的代码集中起来实现模块化。

从关联性的角度看，我们要格外注意相互频繁调用的模块，模块之间的频繁调用通常表明原本应该放在一起的要素被分别放在了不同的模块中。

这时候就需要让合适的单一模块来实现功能，或者将模块功能整合在一起，或者重新创建一个模块来实现相应的功能，总之要保证单一功能的密集性。

 

1.枚举

枚举法，也称作穷举，指的是从问题所有可能的解的集合中一一枚举各元素。题目中给定的检验条件判定哪些是无用的，哪些是有用的。

  优点是算法简单，在局部地方使用枚举法，效果十分好。缺点是运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢。

例题：

百钱买白鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元，母鸡一只5元，小鸡3只1元，试求用100元买100只鸡，各为多少才合适？

解析：

根据题意可以得到方程组:3X+5Y+Z/3=100;X+Y+Z=100;

#include<iostream>
using namespace std;
int main()
{
	int x,y,z;
	for(x=0;x<=100;x++)
	{
		for(y=0;y<=100;y++)
		{
			for(z=0;z<=100;z++)
			{
				if(x+y+z==100&&3*x+5*y+z/3==100&&z%3==0)
					cout<<x<<" "<<y<<" "<<z<<endl;
			}
		}
	}
	return 0;
} 

优化：利用方程组3X+5Y+Z/3=100;X+Y+Z=100;可将Z约去，得到新方程组4X+7Y=100

#include<iostream>
using namespace std;
int main()
{
	int x,y,z;
	for(x=0;x<=25;x++)
	{
		y=100-4*x;
		if(y%7==0&&y>=0)
		{
			y=y/7;
			z=100-x-y;
			if(z%3==0&&3*x+5*y+z/3==100)
				cout<<x<<" "<<y<<" "<<z<<endl; 
		}
	}
	return 0;
} 

2.递推

递推算法是一种简单的算法，即通过已知条件,利用特定关系得出中间推论，直至得出结果的算法。

 

例题：斐波那契数列

因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

fibonacci 数列定义：

n = 1,2 时，fib(n) = 1

n > 2 时，fib(n) = fib(n-2) + fib(n-1)

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,……….

解析：

递归算法

#include<iostream>
using namespace std;
int fib(int n)
{
	if(n<=1)
		return n;
	else
		return fib(n-1)+fib(n-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<fib(n);
	return 0;
}

优化

#include<iostream>
using namespace std;
int fib(int n)
{
	int a=0;int b=1;int c;
	for(int i=2;i<=n;i++)
	{
		c=a+b;
		a=b;
		b=c;
	}
	return c;
}
int main()
{
	int n;
	cin>>n;
	cout<<fib(n);
	return 0;
}

3.贪心算法

所谓贪心算法是指在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

例题：合并果子

现在又n堆果子，第i堆有ai个果子。现在要把这些果子合并成一堆，每次合并的代价是两堆果子的总果子数。求合并所有果子的最小代价。

解析：每次选取最少的两堆合并，直到剩一堆即可。

#include<iostream>
#define maxsize 100
using namespace std;
void sort(int *a,int low,int high)
{
	int i=low,j=high;
	int temp=a[i];
	if(low>high)
		return;
	while(i<j)
	{
		while(i<j&&a[j]>=temp)
			j--;
		if(i<j)
			a[i]=a[j];
		while(i<j&&a[i]<=temp)
			i++;
		if(i<j)
			a[j]=a[i];
	}
	a[j]=temp;
	sort(a,low,i-1);
	sort(a,i+1,high);
}
void merge(int a[],int n)
{
	sort(a,0,n-1);
	int ans=0;
	for(int i=1;i<n;i++)
	{
		a[i]+=a[i-1];
		ans+=a[i];
		int temp=a[i];
		 
		for(int j=i+1;j<n&&a[j]<a[i];j++)
		{
			a[j-1]=a[j];
			a[j]=temp;	
		} 
	}
	cout<<ans<<endl;
}
int main()
{
 	int a[maxsize];
 	int n,i;
 	cin>>n;
 	for(i=0;i<n;i++)
	 	cin>>a[i]; 
	merge(a,n);
	return 0; 
}


 

利用优先队列的方法优化

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而在队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。

 

priority_queue

基本操作：

empty()：如果队列为空，则返回真

pop():删除对顶元素，删除第一个元素

push():加入一个元素

size():返回优先队列中拥有的元素个数

top():返回优先队列对顶元素，返回优先队列中有最高优先级的元素

头文件：#include<queue>

声明方式：

1.普通方法

priority_queue<int> q;//通过操作，按照元素从大到小的顺序出队

priority_queue<int,vector<int>,greater<int>> q;//通过操作，按照元素从小到大的顺序出队

2、自定义优先级：

struct cmp {     

operator bool ()(int x, int y)     

{        

 return　x > y;　　 // x小的优先级高       //也可以写成其他方式，如： return p[x] > p[y];表示p[i]小的优先级高

}

};

priority_queue<int, vector<int>, cmp> q;    //定义方法

//其中，第二个参数为容器类型。第三个参数为比较函数。

3、结构体声明方式：

struct node {     

int x, y;     

friend bool operator < (node a, node b)     

{         

return a.x > b.x;    //结构体中，x小的优先级高     

}

};

priority_queue<node>q;   //定义方法

//在该结构中，y为值, x为优先级。

//通过自定义operator<操作符来比较元素中的优先级。

//在重载”<”时，最好不要重载”>”，可能会发生编译错误

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int,vector<int>,greater<int> >p;
	int n,m;
	int a,b,result=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>m;
		p.push(m);
	}
	while(p.size()>=2)
	{
		int a=p.top();p.pop();
		int b=p.top();p.pop();
		result+=a+b;
		p.push(a+b);
	}
	cout<<result<<endl;
	return 0;
}


 

3.4　变量的作用域
变量的作用域是指变量的作用范围，即定义一个变量后，在哪些地方可以使用这个变量。按照作用域的不同，Python中的变量可分为局部变量和全局变量，下面分别介绍。
3.4.1　局部变量
在一个函数中定义的变量就是局部变量(包括形参)，其作用域是从定义局部变量的位置至函数结束的位置。下面通过一个例子说明局部变量的作用域，参见代码清单3-22。
代码清单3-22　局部变量示例
1    def LocalVar1(x): #定义函数LocalVar1，形参x是局部变量
2        print('LocalVar1中x的值为',x) #输出x
3        x=100 #将x的值修改为100
4        print('LocalVar1中x修改后的值为',x) #输出x
5        #print('LocalVar1中y的值为',y) #取消注释后，该行代***错
6        y=20 #定义局部变量y，将其赋值为20
7        print('LocalVar1中y的值为',y) #输出y
8    def LocalVar2(): #定义函数LocalVar2
9        x=10 #定义局部变量x，将其赋值为10
10       print('LocalVar2中调用LocalVar1前x的值为',x) #输出x
11       LocalVar1(15) #调用LocalVar1函数
12       print('LocalVar2中调用LocalVar1后x的值为',x) #输出x
13       #print('LocalVar2中y的值为',y) #取消注释后，该行代***错
14   LocalVar2() #调用LocalVar2函数
程序执行结束后，将在屏幕上输出如下结果：
LocalVar2中调用LocalVar1前x的值为 10
LocalVar1中x的值为 15
LocalVar1中x修改后的值为 100
LocalVar1中y的值为 20
LocalVar2中调用LocalVar1后x的值为 10
从输出结果中可以看到：
在LocalVar1和LocalVar2中都有名为x的局部变量。在LocalVar1函数中将x的值先赋为15，再改为100；但在LocalVar2中调用LocalVar1函数后，x的值仍然为10，即在LocalVar1中对x所做的修改不会影响LocalVar2中x的值。在不同的函数中，可以定义相同名字的变量，二者不会冲突，虽然同名但代表不同的变量，所以可以存储不同的数据。
在LocalVar1中定义的变量y也是局部变量，其作用域是从定义y的位置到LocalVar1函数结束的位置。如果取消代码清单3-22中第5行代码前面的注释，则系统会给出报错信息“UnboundLocalError: local variable 'y' referenced before assignment”，即在给局部变量y赋值前使用了y；如果取消第13行代码前面的注释，则系统会给出报错信息“NameError: name 'y' is not defined”，即y没有定义。