• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

大一的算法笔记

算法笔记 站点默认 11个月前 (08-19) 279次浏览 已收录 3个评论
文章目录[隐藏]

上学期的算法笔记,有点杂,嘿嘿,有错误,欢迎指正

1.求三个最大数中,老师用了函数,系统函数max,而且是镶嵌套用。
再看自己的代码,可以看出效率的高低。在今后的数量大小比较中,应该学会使用
max系统函数,同时掌握其他系统函数。

#include
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c;
if(a>b)
d=a;
else
d=b;
if(d>c)
cout<<"max="<http://git.webturing.com/AOJTeam/Contest1190/src/ec1961affcbee1e0ff97a2ab90a671a90ec978ad/E.cpp>

2.在cout输出流中,学会灵活运用其输出的表示,,老师这道题解的表示便是相当六。

1. #include
2. using namespace std;
3. int main() {
4. cout << 1 * 2 * 3 * 4 * 5 << endl;5. return 0;}来自 <http://git.webturing.com/AOJTeam/Contest1190/src/ec1961affcbee1e0ff97a2ab90a671a90ec978ad/F.cpp>

3.选择查找,利用while直接循环读取,也正因为if在while 从而实现了多个量的选这查找,
可以知道,while和if连用的魅力之处有多大。

1. #include
2. using namespace std;
3. int main() {
4. int id, score;
5. while (cin >> id >> score) {
6. if (score >= 80) {
7. cout << id << " " << score << endl;8. }9. }10. return 0;来自 <http://git.webturing.com/AOJTeam/Contest1200/src/74ae34753a99ab3e69107116821d64d404c68373/B.cpp>

4素数的判断巧妙运用bool类型,在令人烦恼的for语句中,使用bool将可用信息提出来,再将其运用到之后其他语句中,避免了for中的纷杂

我的代码

1. #include
2. using namespace std;
3. int main() {
4. int n;
5. cin >> n;
6. bool flag = true;
7. for (int i = 2; i <= n - 1; i++)8. if (n % i == 0) {9. flag = false;10. break;11. }12. if (flag) {13. cout << "prime" << endl;14. } else {15. cout << "not prime" << endl;16. }17. return 0;18. }来自 <http://git.webturing.com/AOJTeam/Contest1200/src/74ae34753a99ab3e69107116821d64d404c68373/D.cpp>

#include
using namespace std;
int main() {
int a,b;
cin>>a;
for(int i=2;i
2. using namespace std;
3. int main() {
4. int Max = INT_MIN;
5. for (int i = 0; i < 10; i++) {6. int t;7. cin >> t;
8. Max = max(t, Max);
9. }
10. cout << Max << endl;11. return 0;12. }来自 <http://git.webturing.com/AOJTeam/Contest1200/src/74ae34753a99ab3e69107116821d64d404c68373/E.cpp>

1. #include
2. using namespace std;
3. int main() {
4. int a[10];
5. for (int i = 0; i < 10; i++) cin >> a[i];
6. cout << *max_element(a, a + 10) << endl;7. return 0;8. }来自 <http://git.webturing.com/AOJTeam/Contest1200/src/74ae34753a99ab3e69107116821d64d404c68373/E2.cpp>

6-求三个数大小按顺序输出
swap交换值函数

c++中快速排序函数sort,用于对数组进行排序
默认升序

#include

using namespace std;

int main() {
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
if (b > c) swap(b, c);
if (a > b) swap(a, b);
cout << a << " " << b << " " << c << endl; return 0;}1. #include
2. using namespace std;
3. int main() {
4. int a[3];
5. cin >> a[0] >> a[1] >> a[2];
6. sort(a, a + 3);
7. cout << a[0] << " " << a[1] << " " << a[2] << endl;8. return 0;9. }来自 <http://git.webturing.com/AOJTeam/Contest1200/src/74ae34753a99ab3e69107116821d64d404c68373/F2.cpp>

7-解方程
sqrt开方函数在头文件#include 中可以使用

#include
using namespace std;
int main()
{
int a,b,c;
cin>>a>>b>>c;
double dt=b*b-4*a*c;
if(dt<0) cout<<"no answer"<
2. using namespace std;
3. int main() {
4. for (int i = (int) sqrt(1000); i < 100; i++) {5. int n = i * i;//n is a square number;6. if (n < 1000 || n > 9999)continue;
7. int high = n / 100;
8. int low = n % 100;
9. if (high % 11 == 0 && low % 11 == 0) {
10. cout << n << endl;11. }12. }13. return 0;14. }来自 <http://git.webturing.com/AOJTeam/Contest1204/src/90a93c66218f768206480c2263371a90b04478ab/Caabb.cpp>

阶乘取最后六位

1. #include
2. using namespace std;
3. const int MOD = 1000000;
4. int main() {
5. int n;
6. cin >> n;
7. if (n > 24)n = 24;//注意到25!末尾已经有6个0不会对计算结果产生影响
8. int s = 0;
9. for (int i = 1; i <= n; i++) {10. int p = 1;11. for (int j = 2; j <= i; j++) {12. p = p * j % MOD;13. }14. s = (s + p) % MOD;15. }16. cout << s << endl;17. return 0;18. }来自 <http://git.webturing.com/AOJTeam/Contest1204/src/3598f0b0aa1c065aec2dea4e7d5542d36bd8ffc1/D.cpp>

int T;
cin>>T;
while(T–){
……
}
利用这个结构可以实现多组数据测量啊!!!

– memset()

• str — 指向要填充的内存块。
• c — 要被设置的值。该值以 int 形式传递,但是函数在填充内存块时是使用该值的无符号字符形式。
• n — 要被设置为该值的字节数。

void *memset(void *str, int c, size_t n)

#include
using namespace std;

int main()
{
cout << "Size of char : " << sizeof(char) << endl; cout << "Size of int : " << sizeof(int) << endl; cout << "Size of short int : " << sizeof(short int) << endl; cout << "Size of long int : " << sizeof(long int) << endl; cout << "Size of float : " << sizeof(float) << endl; cout << "Size of double : " << sizeof(double) << endl; cout << "Size of wchar_t : " << sizeof(wchar_t) << endl; return 0;}当上面的代码被编译和执行时,它会产生下列结果,结果会根据使用的机器而不同:Size of char : 1Size of int : 4Size of short int : 2Size of long int : 4Size of float : 4Size of double : 8Size of wchar_t : 4利用以上知识点可以这样初始化数组memset(a,0,sizeof(a));一个思想最小启动计划可以将每一项放入数组中,当然实物不能放入但是可以初始化数组0,一一对应,最后只需要将数组排序,输出a[0],这就是最小启动的次数。知斐波那契数列有如下描述: F(1)=F(2)=1,当 n>=3,F(n)=F(n-1)+F(n-2)。它的前几项可以表示为 1,1,2,3,5,…
当我们需要找写一个算法代码时候如果数组太大则应该考虑到
会有规律,拿这个数列来说,其中的数能被3,4除则n就可以被4和6除
只需要判断n即可。

if(sum – (int)sum == 0)
printf(“%d\n”, (int)sum); //注意这里输出格式的切换
else
printf(“%.1f\n”, sum);
可以判断如果是小数则按小数输出如果不是则按整数输出。

tolower(c)
c为大写字符;
可以将其转化为小写字符。若为其他值则不变。

总结思想

写代码算法前一定要想好解决问题的思路,再去写才不会频繁出差,不然会浪费很多时间

递归函数返回时候是层层返回
#include
void up_and_down(int);
int main(void)
{up_and_down(1);
return 0;
}

void up_and_down(int n)
{printf(“level %d: n loacation %p\n”, n, &n);/*1*/
if (n < 4)up_and_down(n + 1);printf("level %d: n loacation %p\n", n, &n);/*2*/} • c++函数不允许返回一个数组。 • 2C++ 不支持在函数外返回局部变量的地址,除非定义局部变量为 static 变量。 • 3 int *cat(){};并不是指向函数的指针,而是声明一个返回指针的函数。。。强大的getch();存在与头文件#include中。
作用:从控制台去一个字符但是不显示在屏幕上,
getch与getchar基本功能相同,差别是getch直接从键盘获取键值,不等待用户按回车,只要用户按一个键,getch就立刻返回, getch返回值是用户输入的ASCII码,出错返回-1.输入的字符不会回显在屏幕上.getch函数常用于程序调试中,在调试时,在关键位置显示有关的结果以待查看,然后用getch函数暂停程序运行,当按任意键后程序继续运行.

这串小小的代码就可以达到动态数组,惊喜不???
int n;
cin>>n;
int *a=new int[n];//n为数组a的长度。

typedef 还可以掩饰复合类型,如指针和数组。
例如,你不用像下面这样重复定义有 81 个字符元素的数组:
1 charline[81];
2  
3 chartext[81];
只需这样定义,Line类型即代表了具有81个元素的字符数组,使用方法如下:
1 typedef char Line[81];
2  
3 Line text,line;
4  
5 getline(text);
同样,可以像下面这样隐藏指针语法:
1 typedefchar* pstr;
1 intmystrcmp(constpstr p1,constpstr p3);

如何在求在一组m个数据中选n个数进行排列的组合个数。
这和用dfs实现的全排列差不多。
下面的代码用dfs实现了全排列,但是将其稍微改动就可以实现上述所说的效果。
#include
using namespace std;
int a[100],n;
int book[100]={0};
void print(){
for(int i=1;i<=n;i++) cout<>n;
dfs(1);
return 0;
}

关于dfs
dfs的全排列模板与dfs选数的模板(实现了去重)。
dfs全排列模板void dfs(int step){
if(step==n+1){
print();
return;
}
for(int i=1;i<=n;i++){ if(book[i]==0){ a[step]=i; book[i]=1; dfs(step+1); book[i]=0; } } return ;}dfs选数去重模板void dfs(int step){ for(int i=step;i数论

题目描述
给定区间[L,  R]  ,  请计算区间中素数的个数。
输入
两个数L和R。 
输出
一行,区间中素数的个数。 
样例输入
2 11
样例输出
5
bool prime(int n){
if(n==2||n==3)return 1;
if(n%6!=1&&n%6!=5)return 0;
for(int i=5;i<=n/2;i+=6){ if(n%i==0||n%(i+2)==0) return 0; } return 1;}虽然尝试着优化计算素数的时间,但还是失败了,时间超限了。优化依据:这道题用普通方法来判断素数的话必然超限,在别人的博客上看到了一个比较高效的判断素数的方法: 大于等于5的质数一定和6的倍数相邻。例如5和7,11和13,17和19等等;换句话说:不与6的倍数相邻的数一定不是素数,与6的倍数相邻的数不一定是素数。所以我们先排除掉不与6相邻的数,再判断与6的倍数相邻的数是否是素数 素数筛prime[]数组中的素数是递增的,当i能整除prime[j],那么i*prime[j+1]这个合数肯定被prime[j]乘以某个数筛掉。 因为i中含有prime[j],prime[j]比prime[j+1]小,即i=k*prime[j],那么i*prime[j+1]=(k*prime[j])*prime [j+1]=k’*prime[j],接下去的素数同理。所以不用筛下去了。因此,在满足i%prime[j]==0这个条件之前以及第一次 满足改条件时,prime[j]必定是prime[j]*i的最小因子。 #include

using namespace std;

vector Prime(int n) { // 求解n以内(含n)的素数
bool flag[n + 1]; // 标记数组,flag[i]==0表示i为素数,flag[i]==1表示i为合数
memset(flag, 0, sizeof(flag));
vector prime;
int cnt = 0; // 素数个数
for (int i = 2; i <= n; ++i) { if (!flag[i]) { prime.push_back(i); // 将i加入素数表 cnt++; } for (int j = 0; j < cnt; ++j) { // 保证每个合数只会被它的最小质因数筛去 if (i * prime[j] > n) break;
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return prime;
}
int main(int argc, char const *argv[])
{
int n;
while(1) {
printf(“请输入n,将输出n以内(含n)的素数:”);
scanf(“%d”, &n);
if(n < 0) break; vector prime = Prime(n);
int cnt = prime.size();
printf(“一共有%d个素数:\n”, cnt);
for(int i = 0; i < cnt; i++) { printf("%3d ", prime[i]); if(i % 10 == 9) puts(""); } puts("\n"); } return 0;}


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:大一的算法笔记
喜欢 (20)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(3)个小伙伴在吐槽
  1. 路过打卡
    匿名2019-12-19 15:01 回复 Windows 10 | 未知浏览器
  2. 可以的
    rrr超酷2019-12-17 16:29 回复 Windows 7 | Chrome 75.0.3770.100
  3. 大佬你好
    匿名2019-08-24 18:03 回复 Windows 7 | Chrome 64.0.3282.204