coding
二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
int
search(int nums[], int size, int target)
{
int left = 0 ;
int right = size - 1 ;
while(left <= right)
{
int mid = left + ((right - left) / 2) ;
if (nums[mid] > target) right = mid - 1 ;
else if(nums[mid] < target) left = mid + 1 ;
else return mid ;
}
return -1 ;
}
int
search(int nums[], int size, int target)
{
int left = 0 ;
int right = size ;
while(left < right)
{
int mid = left + ((right-left)/2) ;
if(nums[mid] > target) right = mid ;
else if(nums[mid] < target) left = mid + 1 ;
else return mid ;
}
return -1 ;
}
|
猴子吃桃数学推理
最后一天剩1个桃，每一天都计划吃一半的桃子，但是猴子每天都多吃一个，求最开始有几个桃。
把最后一天当作第一天，倒序描述一下，设第 天桃子有 个，由数学逻辑：
这是一个以 为首项， 为公比的等比数列，由递推可得：
计算机中 的幂次直接用 移位运算，移多少位就是 的多少次幂。
1
| cout<< ((1<<(n-1))*3 - 2) <<endl ;
|
集合求和
有一个总数为 n 的整数集合，对于其子集求和：
1.空集为0，直接过
2.先选出指定的一个元素，加入子集：
1):子集有一个元素时，不添加元素了，对其余每个元素来说，均有次选中。
2):有两个元素时，从剩余元素选一个，均有次选中。
:有 i 个元素时，从剩余元素选 个，均有次选中。
所以一共有这么多次被选中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<iostream>
#include<algorithm>
#include<cmath>
#define re register
using namespace std ;
int a[31], i;
long long s = 0;
int
main()
{
while(cin>>a[i++]) ;
for(re int j=0; j<i; j++) s += a[j] ;
s *= pow(2,i-2) ;
cout<<s;
return 0 ;
}
|
C++ 四舍五入
保留整数
1.printf 函数直接打印
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
using namespace std;
int
main()
{
double a = 1.4999999;
double b = 1.5000001;
double n_a = -1.4999999;
double n_b = -1.5000001;
printf("%.0f\n", a);
printf("%.0f\n", b);
printf("%.0f\n", n_a);
printf("%.0f\n", n_b);
return 0;
}
|
2.自己写函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
using namespace std;
int round_0 (double n)
{
if (n > 0)
return n - int(n) >= 0.5 ? int(n)+1 : int(n);
else
return -n - int(-n) >= 0.5 ? -(int(-n) + 1) : -int(-n);
}
int
main()
{
double a = 1.4999999;
double b = 1.5000001;
double n_a = -1.4999999;
double n_b = -1.5000001;
cout << round_0(a) << endl;
cout << round_0(b) << endl;
cout << round_0(n_a) << endl;
cout << round_0(n_b) << endl;
return 0;
}
|
3.cmath 库函数 round
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <cmath>
using namespace std;
int main()
{
double a = 1.4999999;
double b = 1.5000001;
double n_a = -1.4999999;
double n_b = -1.5000001;
cout << round(a) << endl;
cout << round(b) << endl;
cout << round(n_a) << endl;
cout << round(n_b) << endl;
return 0;
}
|
保留小数点后k位
printf 函数要几位打印几位
iomanip 库里的 fixed 和 setpricision
setpricision() 接受一个整型参数，表示保留多少位有效数字
fixed(std::fixed)表示用于 setpricision 的有效数字，针对的是小数点后的有效数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <iomanip>
using namespace std;
int main()
{
double a = 1.499;
double b = 1.500;
double c = 1.48;
double d = 1.5;
double n_a = -1.499;
double n_b = -1.500;
cout << fixed << setprecision(2) << a << endl;
cout << fixed << setprecision(2) << b << endl;
cout << fixed << setprecision(2) << c << endl;
cout << fixed << setprecision(2) << d << endl;
cout << fixed << setprecision(2) << n_a << endl;
cout << fixed << setprecision(2) << n_b << endl;
return 0;
}
|
C++ sort
第一个参数是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。
第二个参数相对较好理解，即首地址加上数组的长度n（代表尾地址的下一地址）。
第三个参数是比较函数的名称（自定义函数cmp），这个比较函数可以不写，即第三个参数可以缺省，这样 sort 会默认按数组升序排序。
简单例子：对数组A的 0~n-1 元素进行升序排序，只要写 sort(A,A+n) 即可；对于向量V也一样，sort(v.begin(),v.end()) 即可。
比如按照每个数的个位进行从大到小排序，可以定义为：
1
2
3
4
5
| bool
cmp(int x,int y)
{
return x % 10 > y % 10 ;
}
|
对结构体排序：
1
2
3
4
5
6
7
8
9
10
| struct node{
string name ;
int score ;
}stu[1005];
bool
cmp(node x, node y)
{
return x.score > y.score ;
}
|
cmp 也可使用标准库函数 functional
1
2
3
4
5
6
7
8
9
10
11
12
|
sort(begin,end,less<data-type>())
sort(begin,end,greater<data-type>())
====================================
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
sort(a,a+20,less<int>()) ;
sort(a,a+20,greater<int>()) ;
|
