总结 Date 2017.09.23
总结 Date 2017.09.23
<1>统计数字
某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*10^9)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。
思路1:桶排序(但数字范围过大,舍)
思路2:自带排序函数(包含头文件#include< algorithm >)
具体代码:
sort(a,a+n);
int k = 0;
for(int i = 0;i<n;i++)
{
b[k][1] = a[i];
if(a[i] == a[i+1])
{
b[k][0]++;
}else{
k++;
}
}
Sort函数的用法:
bool compare(int a,int b)
{
return a>b; // return 0 即 交换
}
sort(a,a+n,compare);
<2>蜜蜂路线
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M小于N,有多少种爬行路线?
思路1:将路线转换为二维地图,两个数组表示前进方式,用搜索回溯算法(果断超时)
思路2:总结出递推式(赤裸裸的斐波那契数列),然后,果断超过long long 类型最大值,考虑高精度。
1 — 3 — 5 — 7………………
—2 —4 — 6………………
具体如下
int k1 = 500;
b[500] = 1,c[500] = 0;
for(int i = 500;i>=500-(n-m)+1;i--)
{
for(int j = 500;j>=k1;j--)
{
a[j] = b[j] + c[j];
}
for(int j = 500;j>=k1;j--)
{
if(a[j] >= 10)
{
a[j-1] += a[j]/10;
a[j] %= 10;
if(j == k1)
{
k1--;
j = 0;
}
}
}
for(int i = k1;i<=500;i++)
{
c[i] = b[i];
}
for(int i = k1;i<=500;i++)
{
b[i] = a[i];
}
}
<3>Hanoi双塔问题
给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序;
任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。
思路1:还是公式,赤裸裸 2*(2^n-1),考虑高精度。
思路2:递归算法,很明显的递归,开冰箱放大象嘛(肯定超过数据类型的最大范围了)
具体如下:
a[300] = 1;
int k = 300;
for(int i = 1;i<=n+1;i++)
{
for(int j = k;j<=300;j++)
{
a[j]*=2;
if(a[j] >= 10)
{
if(j == k)
{
k--;
}
a[j-1] += a[j]/10;
a[j] %= 10;
}
}
}
递归版:
void hannuota(int n)
{
if(n==1)
{
sum++;
}
else{
hannuota(n-1);
sum++;
hannuota(n-1);
}
}
终于,总结完了。
最新文章
- Hibernate框架简述 内部资料 请勿转载 谢谢合作
- java读取properties配置文件总结
- Qt之重写QLabel类
- 【转】Struts1.x系列教程(6):Bean标签库
- 常用应用层协议HTTP、RTSP、RTMP比较
- 《APUE》第四章笔记(1)
- LA_4670_Dominating_Patterns_(AC自动机+map)
- 几个shell自动化脚本(定期清理、磁盘空间、搜寻关键字)
- debian 64位系统中添加对32位的支持
- C++ enum 作用域问题和解决方案
- Java学习笔记——排序算法之进阶排序(堆排序与分治并归排序)
- vue+elementUI+axios实现的全局loading加载动画
- linux使用vim打开乱码问题
- Flask cookie
- environment variable
- 【转载】使用 Google Guava 美化你的 Java 代码
- iOS - Share Extension
- 混沌数学之CircuitChaotic(二维离散电路混沌系统)
- 51Nod 1095 Anigram单词 | Hash
- python基础之re,sys,suprocess模块