/*
编程1 ：求解f(n) = 1-2+3-4+5-6+……+n;
*/
#if 0
int main()
{
int n;
int sign = 1; //符号位
int sum = 0;
cin>>n;
for(int i = 1;i<=n;i++)
{
sum+=i*sign;
sign*=-1; //每次都改变符号位
}
cout<<sum<<endl;
}
#endif/*
编程2：给出一个非负整数数组，最初定位在数组的第一个位置，数组中的每个元素的值代表你在那个位置可以跳跃的最大长度，判断你是否到达数组的最后一个位置
例如： A = {2，3，1，1，4}，返回true, A = {3,2,1,0,4},返回false
*/
#if 0
int jump(int arr[],int n,int x)
{
if(arr == NULL || n == 0)
return 0;
if(x>=n-1) //判断x是否走到最后一个位置
return 1;
for(int i = arr[x];i>0;i--)
{
if(jump(arr,n,x+i) == 1) //递归 数组的元素作为下标传过去继续跳跃
return 1;
}
return 0;
}
int main()
{
int n;
cin>>n;
int *a = new int[n];
for(int i = 0;i<n;i++)
{
cin>>a[i];
}
int ret = jump(a,n,0);
if(ret == 1)
cout<<"true"<<endl;
else
cout<<"false"<<endl;
}
#endif/*
编程3：给定数组，任意相邻两个元素的差的绝对值等于1，设计一个算法，在该数组中可以查找某个元素的位置，如果该元素的值多次出现，返回第一次的位置。
例如：{4,5,6,5,6,7,8,9,10,9},元素9出现了2次，第一次出现的位置是7
*/
/*
解题思路：比如要找y，由于相邻两个数字之差的绝对值为1，设t = abs(y-a[0]),所以在第t个位置之前的的数肯定都比y小，
所以我们不需要依次遍历，直接定位到a[t],重新计算t,再重复上述步骤
这种算法主要利用了当前位置的数与查找数的差来实现跨越式搜索。
*/
#if 0
int FindNumber(int a[],int n,int number)
{
if(a == NULL ||number == 0)
return 0;
int num = abs(number-a[0]);
while(num<n)
{
if(a[num] == number)
return num;
num+=abs(number-a[num]);
}
}
int main()
{
int a[15] = {4,5,6,5,6,7,8,9,10,11,12,11,12,13,12};
int ret = FindNumber(a,15,13);
cout<<ret<<endl;
}
#endif/*
编程4：写函数实现，输入一个不包含重复字符的字符串，输出该字符串中字符的所有组合，
例如，输入abc,输出a,b,c,ab,ac,bc,abc
*/
/*
解题思路：因为要求集合里的元素所能够组成的所有组合，所以我们需要遍历该集合，
这里假设我们的集合为”abc”,从头扫描集合里的元素，第一个元素为a,对于这个元素，
有两种选择，一种是将字符放到组合中，然后在剩下的n-1个字符中选取m-1个字符
另一种是不把字符放到组合中去，接下来需要在剩下的n-1个字符中选取m个字符
*/
#if 0
void Combination(char* string,int number,vector<char>& result)
{
if(number == 0)
{
vector<char>::iterator iter = result.begin();
for(;iter<result.end();++iter)
cout<<*iter;
cout<<endl;
return ;
}
if(*string == '\0')
return ;
result.push_back(*string);
Combination(string+1,number-1,result); //将字符放到组合当中
result.pop_back();
Combination(string+1,number,result); //不把字符放到组合当中
}
void Combination(char* string)
{
if(string == NULL)
return ;
int length = strlen(string);
vector<char>result;
for(int i = 1;i<=length;++i)
{
Combination(string,i,result);
}
}
int main()
{
char* string = "abc";
Combination(string);
return 0;
}
#endif简述题：给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆额外的黑色豆子，重复以下过程，直至罐中仅剩一颗豆子为止。从罐中随机选取两颗豆子，如果颜色相同，就将它们都扔掉并且放入一个额外的黑色豆子，如果颜色不同，就将白色的豆子放回罐中，而将黑色的豆子扔掉。证明该过程会终止。最后留在罐中的豆子颜色与最初的罐中的白色豆子和黑色豆子的数量有什么数学关系。
答案： 题目意思是从罐中随机选取豆子，若颜色相同，扔掉再放入一颗额外的黑色豆子，若颜色不同，将白色豆子放回，黑色豆子扔掉。
一样的道理，不管如何罐中白色豆子的奇偶性一直保持不变， 当白球的个数为偶数时，最后剩下的一球为黑球，当为奇数时，最后剩下的为白球。关于这个问题网上有人写代码实现，大家可以搜索了解。
总结：这次广联达线下笔试，拿到试卷感觉题目不是很难，但是之后我电脑上实现的时候，发现自己在试卷上的手写代码还是有很多小漏洞，
第三道编程题是借鉴别人的思路写的，当时只是想到顺序遍历数组，没有想出更高效的算法，第二题组合问题没有写出来代码，总结下来笔试的不是很好，还是要继续加油。