头像

林带王子




离线:2天前


最近来访(41)
用户头像
南林花样划水冠军彡
用户头像
鱿鱼圈ᰔ
用户头像
林轰轰
用户头像
一塌糊涂
用户头像
yxc的小迷妹
用户头像
昔乙
用户头像
陌丨落
用户头像
可乐_3
用户头像
Vanilla_Cappuccino
用户头像
明璐花生牛奶
用户头像
是一个一个一个CE自动机啊啊啊啊啊啊啊啊啊啊啊啊啊
用户头像
SmiLeeeee
用户头像
asukaqaqzz
用户头像
Kam_1
用户头像
nowornever_7
用户头像
19sm
用户头像
拾一.


题目数据链接

1.初始化令S={v0}, T={剩下顶点} V为全部顶点集合
2.d[i]初值:若 [HTML_REMOVED]存在,那么就把d[i]的值设置为权值,否则就为无穷
3.从T中迭代找出一个距离v0距离最小的顶点vj加入s,根据新加入的顶点vj更新d[i]的值
4.对T中的顶点进行修改
5.重复上述,直至 S = V

错误代码 晚上找一下错误点

```
#include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 100;

int dis[N][N] = {9999};

int n;//几个顶点
int m;//几条边

int d[N];
int v[N];//是否已经放在s集合中

int find()//找距离最小的点,贪心体现在这
{
int ma = 9999;
int temp = 0;
for(int i = 2; i <= n; i ++)
{
if(d[i] < ma) {
ma = d[i];
temp = i;
}
}
return temp;
}

int full()
{
int a = 1;
for(int i = 2; i <= n; i ++)
{
a = a * v[i];
}

return a;

}

int main()
{
scanf(“%d%d”, &n, &m);
for(int i = 1; i <= m; i ++)
{
int j, k, l;
scanf(“%d%d%d”, &j, &k, &l);
dis[j][k] = l;
}

for(int i = 2; i <= n; i ++)
{
    if(dis[1][i] < 9999) d[i] = dis[1][i];//最初的数据进去
    else d[i] = 9999;
}

v[1] = 1;//第一个顶点放进去了

int t = full();//返回s集合是否已经包含所有顶点

int p = find();//找到距离1顶点最小的顶点

v[p] = 1;//把找到的顶尖加入集合
t = full();

while(!t)//s集合是否已经全部包含所有顶点
{
    for(int i = 2; i <= n; i ++)
    {
        if(d[i] > d[p] + dis[p][i]);
        d[i] = d[p] + dis[p][i];
    }
    p = find();
    v[p] = 1;
    t = full();
}
return 0;

}
```




贪心:以逐步的局部最优,达到最终的全局最优。要依照某种策略。策略“只顾眼前,不管将来”。

1.币种统计问题
某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱,且取款的张数最少,
取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。
QQ图片20221120144824.png
方法:大的币值能取多少张就取多少张,先考虑在当前币值情况下的最优解,为了
使得最终的张数最少 那么在当前较大的币值情况下就要多换成大的币值

#include<iostream>
#include<cstring>

using namespace std;

int main()
{
    int money;
    scanf("%d", &money);
    int count = 0;
    int a[8] = {0, 100, 50, 20, 10, 5, 2, 1};
    for(int i = 1; i <= 7; i ++)
    {
        count += money / a[i];
        money = money % a[i];
    }
    printf("%d", count);
    return 0;
}

!!!请注意
某国的币种是这样的,共9种:100,70,50,20,10,7,5,2,1。
这种情况下,刚才的贪婪算法是否能够求得最优解?
在这样的币值种类下,再用贪婪算法就行不通了,比如某人工资是140,按贪婪算法140=100(1张)+20(2张)
共需要3张,而事实上,只要取2张70面额的是最佳结果,这类问题可以考虑用动态规划算法来解决
因为,7、70破坏了“取最优”的贪婪策略的正确性
具体问题将留到动态规划章节再进行探究

2.活动安排问题
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:
!!!求最大的相容活动子集合。
QQ图片20221120150039.png
这套题怎么用贪心来做?前一题的要求很明确,即最少的币值数量,这一题是最大的活动安排场数
如果只是 比如0时刻就考虑当前能去上的持续时间较短的活动 那么是不是也就满足了局部最优解?
如何通过局部最优解求全局最优解呢?
找结束时间!!
选择具有最早结束时间的相容活动加入,使剩余的可安排时间最大,以安排尽可能多的活动。
该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
acwing 4176

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1010;

typedef pair<int, int> Pi;
#define start first
#define end second
Pi st[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) 
     scanf("%d%d", &st[i].end, &st[i].start);

    sort(st, st + n + 1);

    for(int i = 1; i <= n; i ++)
    {
        swap(st[i].start, st[i].end);
    }

    int count = 1;//默认选择最早结束的为第一个加入的活动

    int now = 1;//当前为第一个互动

    for(int i = 2; i <= n; i ++)//从第二个活动开始比较
    {
        if(st[i].start >= st[now].end)//如果紧接后面的开始时间大于前一个活动的结束时间,那么下一个活动
                                      //就是活动i
        {
            count ++;
            now = i;//讲当前活动更新为i
        }
    }

    printf("%d", count);

    return 0;
}

3.
键盘输入一个高精度的正整数N,去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小。
原本的想法:输入完初始值之后从大到小排列 取前面几个数字就行
错误!!!!
要尽量从高位剔除数字大的数字 那么如何从较高位去剔除呢?
如何判断这个位是否该被剔除
简化到只有两位数 1 5 剔除一个 我们是怎么选择剔除5的 那就是1和5做了比较
所以这个地方我们仍然可以相邻两个数字作比较
如果一个数字最高位到最低位是递增的 那么就已经达到最小了
所以要比较的是前一位与后一位是否为递增关系

有错误的写法

int main()
{
   scanf("%d%d", &n, &s);
   for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
   int count = 0;
   for(int i = 1; i <= n; i ++)
   {
       if(count == s) break;
       if(a[i + 1] <= a[i]){
           a[i] = 0;
           count ++;
       }
   }
   for(int i = 1; i <= n; i ++)
   {
      printf("%d", a[i]);
   }
   return 0;
}

这个写法错误在于 如果例如 4 6 3 这里 我们把6剔除之后
本应该变成 4 3这时候要再剔除4 可是我们的比较只与前一位 这时候6变成了0
所以出现了错误
若删除第i位后,必须向前考虑第i-1位与第i+1位进行比较,才能保证结果的正确性。
当删除掉一些数字后,结果的高位有可能出现数字“0”,直接输出这个数据不合理,要将结果中高位的数字“0” 删除掉,再输出。

怎么删除单个元素,是直接删除用后面的顶替上来还是怎么样?
1.直接删除 通过后面去顶替前面的数组元素 PPT做法
2.我们用一个状态数组来表示是删除了还是没删除,这样下来算法需要在其他方面考虑

算法设计1:每次删除元素之后从头开始比较
算法设计2:每次删除之后往前退一位进行比较,这样的算法效率更高一些

选择直接删除方法和算法设计2
在这里还要单独判断被删除后的数组最前面是不是有0 拒绝存在输出003这样的情况
通过遍历数组找到第一个非0元素返回下标

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N];

int n;
int s;
void change(int aim)
{
    for(int i = aim + 1; i <= n; i ++) a[i - 1] = a[i];
    n --;
}
int main()
{
   scanf("%d%d", &n, &s);
   for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
   int count = 0;
   int i = 1;
   while(i <= n - 1)
   {
       if(count == s) break;
       if(a[i] > a[i + 1]){
           change(i);
           count ++;
           i --;
       }else{
           i ++;
       }
   }
   int zero_ = 0;
   for(int i = 1; i <= n; i ++)
   {
      if(a[i] != 0)  zero_ = i;
   }

   for(int i = zero_; i <= n; i ++)
   {
      printf("%d", a[i]);
   }

   return 0;
}

4.数列极差问题
在黑板上写N个正整数排成一个数列,进行如下操作:每一次擦去其中的两个数a和b,
然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中
,最大的记作max,最小的记作min,则该数列的极差定义为M=max-min。

问题分析:
要求数列的极差 经过三个数字的推到和证明
QQ图片20221122143322.png
三个数字的MIN依次取最大的两个数字计算 在对剩下的两个数算出来
MAX依次取最小的两个数字计算,再对剩下的两个数算
那么对于n个数字 也是每次都去最大的两个,最小的两个计算.....

如何取得就有了问题 这里应该要用到两个数组 再输入之后b[i]=a[i];就可以构造成两个一样的数组了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 100;
int a[N];
int b[N];
int n;
int j, k;

void min2(int le)//找出最小的两个数字
{
    if(a[1] < a[2]) {j = 1; k=2;}
    else{
        j = 2;
        k = 1;
    }
    for(int i = 3; i <= n; i ++)
    {
        if(a[i] < a[j]) {k = j; j = i;}
        else if(a[i] < a[k]) {k = i;}
    }
}
void max2(int le)//找出最大的两个数字
{
    if(b[1] > b[2]) {j = 1; k = 2;}
    else {
        j = 2;
        k = 1;

    }
    for(int i = 3; i <= n; i ++)
    {
        if(b[i] > b[j]){k = j; j = i;}
        else if(b[i] > b[k]){k = i;}
    }
}



int calmax(int l)//计算MAX
{
    while(l > 2){
        min2(l);
        a[j] = a[j] * a[k] + 1;
        a[k] = a[l];
        l --;
    }
    return (a[1] * a[2] + 1);
}
int calmin(int l)//计算MIN
{
    while(l > 2){
        max2(l);
        b[j] = b[j] * b[k] + 1;
        b[k] = b[n];
        l --;
    }
    return (b[1] * b[2] + 1);
} 


int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) 
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    int Max = calmax(n);
    int Min = calmin(n);

    printf("%d", Max - Min);

    return 0;
}

4.设计一个算法, 把一个真分数表示为埃及分数之和的形式。所谓埃及分数,是指分子为1的分数。
如:7/8=1/2+1/3+1/24。

思想:
基本思想:逐步选择分数所包含的最大埃及分数,这些埃及分数之和就是问题的一个解。
如:7/8>1/2,
7/8-1/2>1/3,
7/8-1/2-1/3=1/24。
过程如下:
1)找最小的n(最大的埃及分数1/n),使分数f>1/n;//这里最好不要只用循环去套,换个方法
2)输出1/n;
3)计算f=f-1/n;
4)若此时的f是埃及分数,输出f,算法结束,否则返回1)

记真分数F=A/B;对B/A进行整除运算,商为D,余数为0<K<A,它们导出关系如下:
B=A*D+K,B/A=D+K/A<D+1,A/B>1/(D+1),记C=D+1。
这样分数F所包含的“最大”埃及分数就是1/C。

算法步骤
1)设某个真分数的分子为A(≠1),分母为B;
2)把B除以A的商的整数部分加1后的值作为埃及
分数的一个分母C;
3)输出1/C;
4)将A乘以C减去B作为新的A;
5)将B乘以C作为新的B;
6)如果A大于1且能整除B,则最后一个分母为B/A;
7)如果A=1,则最后一个分母为B;否则转步骤2)。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 10010;
int m, n;

int main()
{
    scanf("%d%d", &m, &n);
    while(m != 1)
    {
      int a = n / m;
      a = a + 1;//要输出的埃及分数分母部分
      printf("1/%d ", a);

      m = m * a - n;//算剩下有多少
      n = n * a;

      if(n % m == 0) {
          n = n / m;
          m = 1;
      }
    }
    printf("1/%d", n);
    return 0;
}

相对贪婪问题

5.有2个人轮流取2n个数中的n个数,取数之和大者为胜。请编写算法,让先取数者胜,模拟取数过程。
若取数者能看到全部2n个数
数学建模:我们假设取数顺序只有奇,偶之分
那么如果我们取奇数,那么电脑只能取偶数;如果我们取偶数,电脑只能取奇数
所以我们只要算出奇和偶哪个合起来大 这样就得出了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 1010;
int n;

int main()
{
    scanf("%d", &n);
    int r1, r2;
    for(int i = 1; i <= n; i ++)
    {
        int s;
        scanf("%d", &s);
        if(i % 2 == 1) r1 += s;
        else r2 += s;
    }
    if(r1 > r2) printf("奇数取值");
    else printf("偶数取值");

    return 0;
}

6.多机调度问题
设有n个独立的作业{1,2,…, n },由m台相同的机器进行加工处理。
作业i所需的处理时间为ti 。现约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理
作业不能拆分成更小的子作业。
多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
9@L55}@H$H1L$AHD1$U{BSC.png
如果对作业消耗时间从小到大进行排序之后进行安排作业
设7个独立作业{1,2,3,4,5,6,7}由3台机器M1,M2和M3加工处理
QQ图片20221122183347.png
这样得出的结果显然不是最小的
那么如果倒过来,将作业按时间顺序从大到小进行排列之后再按照刚刚的方法去做
QQ图片20221122183621.png
此时得到的时间为10
这个做法并不能够保证解法一定正确的,但已经是很优秀的解法
想法:先放大的,然后剩下的用小的去一个一个排,剩下的去排给结束时间前的作用机是为了尽可能的将三台机器的
耗时平均下来,这样才有可能使得时间最短

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100;
int t[N];
int mac[N];//表示每个机器的结束时间
int n;
int m;
int find()
{
    int ma = 99999;
    int temp = 1;
    for(int i = 1; i <= m; i ++)
    {
        if(mac[i] < ma){
            ma = mac[i];
            temp = i;
        }
    }
    return temp;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);

    sort(t + 1, t + n + 1, greater<int>());//从大到小排序

    for(int i = 1; i <= m; i ++) mac[i] += t[i];//让m个机器分别另一个最大任务回去

    for(int i = m + 1; i <= n; i ++)
    {
        int r = find();
        mac[r] += t[i];
    }

    // for(int i = 1; i <= m; i ++) printf("%d ",mac[i]);

    int mi = 0;
    int res = 0;
    for(int i = 1; i <= m; i ++)
    {
        if(mac[i] > mi){
            mi = mac[i];
            res = i;
        }
    }

    printf("%d", mac[res]);

    return 0;

}

7.背包问题
物品可切一部分放入;
背包里装的物品的总重量不超过背包的载重量;
背包里装的物品的价值最高者获胜。
想法:
既然物品可以切割,在背包的载重量一定的情况下,优先选择单位价值高的物品放入、

8.构造哈夫曼树方法
没有例题
如果只有两个结点 那么要使得带权路径长度最小 即 w1l1+w2l2++++wi*li最小
在每个结点权值已经确定的情况下 只能尽量使两个的路径最短
而路径最短就可以想到把这两个结点放在同一层(第一层),这样路径就都是1了
由此完成两个结点的哈夫曼树的构造方法,对于多个结点
采用贪心策略 只关注眼前 想使得每一步的最小带权路径长度
对于多个结点的情况 只需要选择最小的两个点先行构造成一个结点 再将构造好的结点重新作为
一个新的结点加入原先的结点序列中 依次类推 知道只剩两个结点

9.单源最短路径 Dijkstra
给定一个带权有向图G=(V,E),V={1,2,…,n },其中每条边的权是一个非负实数。给定一个顶点 v,称为源。
单源最短路径问题:求从源到各顶点的最短路长度(路径上各边权之和)。

如何采用贪心?




蛮力策略应用:选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等。
比较常用还有枚举法、盲目搜索算法等。
1.百钱百鸡问题。
中国古代数学家张丘建在《算经》中提出了著名的“百钱百鸡问题”:
鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一
;百钱买百鸡,翁、母、雏各几何?
算法优化的地方:在确定公鸡和母鸡的数量后(循环),小鸡的数量不需要再列举
直接通过100 - i - j就可以算出了

int main()
{
    for(int i = 0; i <= 20; i ++)
       for(int j = 0; j <= 100 - i; j ++)//100-i也可以用33代替 发现循环次数还减少了
         {  
             int k = 100 - i - j;
             if((i + j + k) == 100 && (5 * i + 3 * j + k / 3.0) == 100) 
             ("%d %d %d \n", i, j, k);
         }

    return 0;
}

2.解数字迷
A B C A B
× A
= D D D D D D
将算式变形为除法:DDDDDD/A=ABCAB。此时只需枚举A:3——9 D:1——9,
共尝试7*9=63次。每次尝试,测试商的万位、
十位与除数是否相同,千位与个位是否相同,都相同时为解。

int main()
{
    for(int d = 1; d <= 9; d ++)
       for(int a = 3; a <= 9; a ++)
       {
           int sd = d * 111111;
           int m = sd / a;
           int st[6];
           for(int i = 1; i <= 5; i ++)
           {
               st[i] = m % 10;
               m = m / 10;
           }
          if((st[5] == st[2] && st[2] == a) && (st[1] == st[4]))
          printf("%d %d %d %d\n", a, st[1], st[3], d);
       }

    return 0;
}

3.编程打印有如下规律的n×n方阵。
0 1 1 1 0
2 0 1 0 4
2 2 0 4 4
2 0 3 0 4
0 3 3 3 0
找到关于方阵划分的依据 一个是i > j or i < j 即左上到右下的对角线
其他另外一个对角线往往跟i + j有关 发现这个对角线上i + j =6
所以划分依据就变成了 i + j是否大于n + 1

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1010;
int che[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
      for(int j = 1; j <= n; j ++)
      {
          if(i < j && i + j < n + 1) che[i][j] = 1;
          if(i > j && i + j < n + 1) che[i][j] = 2;
          if(i > j && i + j > n + 1) che[i][j] = 3;
          if(i < j && i + j > n + 1) che[i][j] = 4;
      }
    for(int i = 1; i <= n; i ++)
     {
           for(int j = 1; j <= n; j ++)
       {
           printf("%d ", che[i][j]);
       }
       puts("");
     }
    return 0;
}

4.狱吏问题
某国王对囚犯进行大赦,让一狱吏n次通过一排锁着的n间牢房,每通过一次,按所定规则转动n间牢房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上;通过n次后,门锁开着的,牢房中的犯人放出,否则犯人不得获释。
转动门锁的规则是这样的,第一次通过牢房,要转动每一把门锁,即把全部锁打开;第二次通过牢房时,从第二间开始转动,每隔一间转动一次;第k次通过牢房,从第k间开始转动,每隔k-1 间转动一次;问通过n次后,哪些牢房的锁仍然是打开的?

一个经典的开关问题 其中可以用到乒乓公式 st[i] = 1 - st[i]
再来就循环体对于每次开关序号的选择 k从1开始 k * i为要关闭或打开的门 最外层循环就是i的循环
里面的whileU循环用来给K增加值

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1010;
int st[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)//代表第n次通过牢房
    {
        int k = 1;
        while(k * i <= n)
        {
            st[k * i] = 1 - st[k * i];
            k ++;
        }
    }
    for(int i = 1; i <= n; i ++){
     if(st[i] == 1) printf("%d ", i);
    }
    return 0;
}

5.螺旋阵:任意给定n值,按如下螺旋的方式输出方阵:
n=3 输出: 1 8 7
2 9 6
3 4 5
思路一:n方阵有固定的层数,层数为n / 2
对于每层都是逆时针赋值 对于每一层都可以分成四段来解决
QQ图片20221119220200.png

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1010;
int st[N][N];
int n;
int main()
{
    scanf("%d", &n);
    int m = n / 2;//层数
    int k = 1;//从1开始给里面赋值
    for(int i = 1; i <= m; i ++)
    {
        int j;
        for(j = i; j <= n - i; j ++) st[j][i] = k ++;
        for(j = i; j <= n - i; j ++) st[n + 1 - i][j] = k ++;
        for(j = n + 1 - i; j >= i + 1; j --) st[j][n + 1 -i] = k ++;
        for(j = n + 1 - i; j >= i + 1; j --) st[i][j] = k ++;
    }
    for(int i = 1; i <= n; i ++)
     {
           for(int j = 1; j <= n; j ++)
       {
           printf("%3d", st[i][j]);
       }
       puts("");
     }
    return 0;
}



  1. 递归实现指数型枚举
    输入样例:3
    输出样例:
    3
    2
    2 3
    1
    1 3
    1 2
    1 2 3
    本题的关键在于,对于选或者不选要有一个方法来帮助我们判断
    引入状态表示数组 st 当st = 1 or 2时 分别表示 选或者不选
    那么就类似于一个dfs的功能 从第一个数字深入到最后一个数字
    每个数字去选择 选或者不选 然而 选或者不选 一个状态结束之后都要完成还原的过程 st = 0代表未考虑
    第一次无论st = 1或者2 都可以不还原 但是第二次就要把他还原到0 代码意思在24行 注释或者不注释 运行结果相同
#include<iostream>
#include<cstring>

using namespace std;
const int N = 16;
int n;
int st[N];//状态 0代表还没考虑 1代表选 2代表不选

void dfs(int a)
{
    //结束判断要写好
    if(a > n)
    {
        for(int i = 1; i <= n; i ++)
        {
            if(st[i] == 1) printf("%d ", i);
        }
        puts("");//每种情况结束之后赚到下一行
        return;
    }

    st[a] = 1;//不选
    dfs(a + 1);
    // st[a] = 0;//恢复现场

    st[a] = 2;
    dfs(a + 1);
    st[a] = 0;
}
int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

2.递归实现排列型枚举
即实现全排列
想一想 素数环问题怎么根据这道题改变
要实现全排列 首先需要一个数组存每次输出的顺序
还需要一个数组来表明 一个数字是否被选择过 所以用布尔型数组就可以了
在dfs函数中 除了边界条件的函数体之外 外加一个循环完成给数组存放数字 最后输出

#include<iostream>
#include<cstdio>

using namespace std;
const int N = 10;

int st[N];//表示每个数组里面放了什么数字
bool si[N];//表示有没有选择这个数字
int n;

void dfs(int a)
{
    if(a > n)
    {
        for(int i = 1; i <= n; i ++) printf("%d ", st[i]);
        puts("");
        return;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!si[i])
        {
            st[a] = i;
            si[i] = true;
            dfs(a + 1);

            //恢复现场
            st[a] = 0;
            si[i] = false;
            // dfs(a + 1);
        }
    }
}

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

3.简单斐波那契数列
输入n 输出前n项
简单for循环

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 50;
int a[N];
int n;

int main()
{
    scanf("%d", &n);
    a[1] = 1;
    for(int i = 2; i < n; i ++)
     a[i] = a[i - 1] + a[i - 2];
    for(int i = 0; i < n; i ++)
     printf("%d ", a[i]);
    return 0;
}



1.求完数 编算法找出1000以内所有完数
完数为 除了自己本事的因子加起来等于这个数

#include<iostream>
using namespace std;

bool f(int n)
{
    int res = 0;
    for(int i = 1; i < n; i ++)
    {
        if(n % i == 0) res += i; 
    }
    if(res == n) return true;
    else return false;
}

int main()
{
    for(int i = 1; i <= 1000; i ++)
    {
        if(f(i)) printf("%d\n", i);
    }
}

2.编写算法:根据参数n打印具有下面规律的图形,如,当n=4时,图形如下:
1
5 2
8 6 3
10 9 7 4
思路:斜行i取值(1~n) 列j取值(1~n+1-i)
关键问题:第i斜行、j列的数据对应于第几行第几列的元素? a[i-1+j][j]
如何把应该为2的映射到数组中第二行第二列呢?我们按照斜着来看
两层循环来嵌套给数组赋值最后输出
每一层循环中循环次数不同 这主要取决于循环到第几层了 n+1-i
第一层循环代表的是第一列 第二列....
第二层循环的是行数 每次都要从1开始 因为每层都是有第一列的元素

#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    int k = 1;
    for(int i = 1; i <= n; i ++)
       for(int j = 1; j <= n + 1 - i; j ++)
       {
           //1,2 = 2,2   1,3 = 3,3 1,4 = 4,4
           a[i + j - 1][j] = k;
           k ++;
       }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= i; j ++)
        printf("%d ", a[i][j]);
        puts("");
    }
    return 0;
}

## _重要!!递归的关键在于找出递归方程式和递归终止条件_

3.汉诺塔
经典的递归思想 要想解决n层的汉诺塔,就一定要解决n-1层的汉诺塔…
最后就是要解决1层的汉诺塔
把n个盘子抽象地看作“两个盘子”,上面“一个”由1——n-1号组成,下面“一个”就是n号盘子。
hanoi(n,a,c,b),表示把n个盘子从a搬到c,可以借助b
则汉诺塔问题hanoi(n,a,b,c)等价于以下三步:
第一步,hanoi(n-1,a,c,b);
第二步,把下面“一个”盘子从a基座移到b基座;
第三步, hanoi(n-1,c,b,a)。
至此找出了大规模问题与小规模问题的关系。

#include<iostream>
using namespace std;
const int N = 1010;

void hanoi(int n, char a, char b, char c)//a到b 可以借助c
{
    if(n > 0)
    {
        hanoi(n - 1, a, c, b);
        printf("%d %c %c \n", n, a, b);
        hanoi(n - 1, c, b, a);
    }

}
int main()
{
    int n;
    scanf("%d", &n);
    char a = 'A';
    char b = 'B';
    char c = 'C';
    hanoi(n, a, b, c);
    return 0;
}

4.大整数存储及运算
求N! 用数组存放数据
难点在于如何满10之后的进位操作
高精度:一位一位的乘,碰到进位就往前传递值,从前到后其实是真实
数字的倒过来,所以最后要从后往前输出
那怎么找到那个最后的数字呢?找到第一个不等于0的数字返回下标就行

#include<iostream>
using namespace std;
const int N = 1010;
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    a[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        int ind = 0;//进位
        for(int j = 1; j < N; j ++)
        {
            int b = a[j] * i + ind;
            a[j] = b % 10;
            ind = b / 10;
        }
    }
    int m = 1;
    for(m = N - 1; m >= 1; m --)
    {
        if(a[m] != 0) break;
    }
    // printf("%d\n", m);
    for(int i = m; i >= 1; i --)
    {
        printf("%d", a[i]);
    }

    return 0;
}



1.求m n的最大公因子
如果n = 0, 计算停止返回m, m即为结果;否则继续2。
记r为m除以n的余数,即r=m mod n。
把n赋值给m,把r赋值给n,继续1。

int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    while(n)
    {
        int r = m % n;
        m = n;
        n = r;
    }
    printf("%d", m);

    return 0;
}

2.开灯问题
从前,有从1到n依次编号的n个同学和n盏灯。1号同学将所有的灯都关掉;
2号同学将编号为2的倍数的灯都打开;3号同学则将编号为3的倍数的灯作相反处理
(该号灯如打开的,则关掉;如关闭的,则打开);以后的同学都将自己编号的倍数的灯,
作相反处理。问:经n个同学操作后,哪些灯是打开的?

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;
int st[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) st[i] = 0;//肯定会有人,所以这里先算第一个同学已经关灯了
    for(int i = 2; i <= n; i ++)
    {
        int k = 1;
        while(k * i <= n)//代表第k * i个同学的操作 
        {
            st[k * i] = 1 - st[k * i];//乒乓开关 等价于见1变0 见0变1
            k ++;
        }
    }
    for(int i = 1; i <= n; i ++) printf("%d ", st[i]);

    return 0;
}

3.输入n个数据,判断是否有两个以上相等的数据
循环比较的话 需要两层循环 需要比较(n-1+n-2+…+1)次
通过引入标志量记录数据是否有重复的情况,相当于整合每趟循环中的比较结果

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;
int st[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &st[i]);
    int flag = 1;
    for(int i = 1; i <= n - 1; i ++)
       for(int j = i + 1; j <= n; j ++)
          if(st[i] == st[j])
          {
              flag = 0;
              break;
          }
    if(flag == 1) puts("yes");
    else puts("no");

    return 0;
}

4.冒泡排序
每躺只选择最大的或者最小的完成排序
递增和递减第二层循环不一样

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10010;
int st[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &st[i]);
    for(int i = 1; i < n; i ++)
       for(int j = i + 1; j <= n; j ++)
       {
           if(st[i] > st[j]) swap(st[i], st[j]);
       }
    for(int i = 1; i <= n; i ++) printf("%d ", st[i]);
    return 0;
}

5.警察抓小偷
警察局抓了a,b,c,d四名偷窃嫌疑犯,其中只有一人是小偷。
审问中a说:“我不是小偷。”b说:“c是小偷。” c说:“小偷肯定是d。”d说:“c在冤枉人。”现在已经知道四个人中三人说的是真话
一人说的是假话,问到底谁是小偷?
问题分析:可通过循环,每次假设一名嫌疑犯为小偷,代入问题系统,检验是否只有一句假话。
用变量x存放小偷的编号,则x的取值范围从1取到4,就假设了他们中的某人是小偷的所有情况。
四个人所说的话就可以分别写成
a说的话:x<>1
b说的话:x=3
c说的话:x=4
d说的话:x<>4或not(x=4)
注意:在x的枚举过程中,当这四个逻辑式的值相加等于3时
,即表示“四个人中三人说的是真话,一人说的是假话”。
if ((x!=1)+(x==3)+(x==4)+(x!=4)==3)

#include<iostream>
using namespace std;

int main()
{
    for(int i = 1; i <= 4; i ++)
    {
        if(((i != 1) + (i == 3) + (i == 4) + (i != 4)) == 3)
        printf("%d", i);
    }
    return 0;
}

6.数组移位
数组中有n个数据,要将它们顺序循环向后移k位,即前面的元素向后移k位,
后面的元素则循环向前移k位,例:0、1、2、3、4循环移3位后为: 2 、3、4、0、1。考虑到n会很大,不允许用2*n以上个空间来完成此题

做法一
用两个一个循环搞定
其中平移之后最后几个会超过数组范围的用(i + m) & n
调整到数组最左边

#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);
    m = m % n;//防止m比n大 计算之后不影响结果
    for(int i = 1; i <= n; i ++)
    {
        int t = (i + m) % n;
        if(!t) b[n] = a[i];
        else b[t] = a[i];
    }
    for(int i = 1; i <= n; i ++) printf("%d ", b[i]);

    return 0;
}

7.求N!
递归做

#include<iostream>
using namespace std;

int fact(int n)
{
    if(n == 1) return 1;
    return n * fact(n - 1);
}
int main()
{
    int n;
    scanf("%d", &n);
    int res = fact(n);
    printf("%d", res);

    return 0;
}

8.爬楼梯
一个楼有n个台阶,有一个人上楼有时一次跨一个台阶,有时一次跨两个或三个台阶,
编写一个算法,计算此人有几种不同的上楼方法,并分析算法的时间复杂度。
难点在于怎么选择每次跨越几次才能保证不重复....
类似于跳台阶问题
用递归 递归函数里面该怎么写呢
!!!!可以如果是三个台阶 那么可以分为两个台阶+一个
因为一个台阶的方法只有一个 两个台阶的方法只有两个
利用这两个已知的答案完成递推

#include<iostream>
#include<cstdio>

using namespace std;
int n;
int res;

int f(int n)
{
    if(n < 0) printf("error!");
    if(n == 1) return 1;//一个台阶的走法只有一个
    if(n == 2) return 2;//两个台阶的走法有两个
    if(n == 3) return 4;
    else return (f(n - 1) + f(n - 2) + f(n - 3));

}
int main()
{
  scanf("%d", &n);
  int a = f(n);
  printf("%d", a);

  return 0;
}


活动打卡代码 AcWing 112. 雷达设备

选择最小的覆盖点数 这里的难点主要是如何将二维的坐标转换在一维的x轴上
可以选择每一个点看极限状态下在x轴上可以接受的雷达坐标范围作为哪个小岛的接收范围
接着排序也很重要 从坐标的最左边开始一个一个往后 判断是否能覆盖
其中double的不能忘记 不能只设置Int型 这样会丢失精度对结果造成影响

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

//定义左端点与右端点
#define left first
#define right second

typedef pair<double, double> Pi;
const int N = 1010;
Pi loc[N];
int n;
int d;

int main()
{
    scanf("%d%d", &n, &d);
    bool boundry = true;//特判 是否有一个点注定不能被覆盖到

    for(int i = 1; i <= n; i ++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(y > d) boundry = false;

        //要注意算距离最好是double
        double dx = sqrt(d * d - y * y);

        //找到每个线段的起始点和终点
        //为了按照second排序,将左右端点互换
        loc[i].right = x - dx;
        loc[i].left = x + dx;
    }

    int res = 0;
    sort(loc + 1, loc + 1 + n);

    //忘记先排序了,按照右端点先排个序
    //sort是按照first排序
    //排完序之后再换回来方便编写下面的程序
    for(int i = 1; i <= n; i ++)
    {
        swap(loc[i].left, loc[i].right);
    }

    if(!boundry) printf("%d", -1);
    else
    {
        double l = -9999;
        for(int i = 1; i <= n; i ++)
        {
            if(loc[i].left > l){
                res ++;//增加一个雷达点
                l = loc[i].right;//更新l的位置
            }
        }

        printf("%d", res);
    }
    // printf("%d", res);

    return 0;

}


活动打卡代码 AcWing 122. 糖果传递

1.jpg

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1000010;

typedef long long ll;

int candy[N];

ll su[N];

int n;

int main()
{
    scanf("%d", &n);

    //这里有问题  sum很大 最好设置成long long 型号
    ll sum = 0;

    for(int i = 1; i <= n; i ++) 
    {
        scanf("%d", &candy[i]);
        sum += candy[i];
    }

    int avg = sum / n;

    for(int i = 1; i <= n; i ++)
       su[i] = su[i - 1] + avg - candy[i];

    sort(su + 1, su + n + 1);//排序

    int mid = (1 + n) / 2;

    ll res = 0;//算总的距离了

    for(int i = 1; i <= n; i ++)
    {
        res += abs(su[mid] - su[i]);
    }

    printf("%lld", res);

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

暴力 4/6个数据 超时了
先统计最远的商店距离 然后从第一个位置作为货仓地址依次比较

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;
int loc[N];
int n;

int f(int i)
{
    int d = 0;
    for(int j = 1; j <= n; j ++)
    {
        d += abs(i - loc[j]);
    }
    return d;
}
int main()
{
    scanf("%d", &n);
    int ma = 0;
    for(int i = 1; i <= n; i ++) 
     {
         scanf("%d", &loc[i]);
         ma = max(ma, loc[i]);
     }
    int mi = 99999999;
    //二分法感觉也不能用 并不能够确定mid的左边和右边
    //哪一边的商店数量多 并不是平均排列
    // int l = 1;
    // int r = ma;
    // while(l < ma)
    // {
    //     int mid = (l + r) / 2;
    // }
    for(int i = 1; i <= ma; i ++)
    {
        int dt = f(i);
        mi = min(mi, dt);
    }

    printf("%d", mi);

    return 0;
}

y总 贪心算法
算贪心吗?应该只有分组 从数学角度看
取A1 AN,A2 AN-1....每两个一对
对于每一对求|c-A1|+|c-AN|的最小值 此时最小值为AN-A1
对于其他剩下的几对都是一样的做法

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;
int loc[N];
int n;

int f(int mid)
{
    int d = 0;
    for(int j = 0; j < n; j ++)
    {
        d += abs(loc[mid] - loc[j]);
    }
    return d;
}
int main()
{
    scanf("%d", &n);

    for(int i = 0; i < n; i ++) 
         scanf("%d", &loc[i]);

    sort(loc, loc + n);

    int mid = n / 2;//取最中间的数字

    int mi = f(mid);

    printf("%d", mi);

    return 0;
}


活动打卡代码 AcWing 1055. 股票买卖 II

贪心做 即遇涨就买
为什么? 因为买了如果隔了很长一段时间,是可以把这个分割多个时间段
跨度超过一天的交易一定可以等价于若干个跨度等于一天的交易

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

const int N = 100010;
int price[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &price[i]);
    //三个循环肯定可以 但是要优化 三个循环分别就是左边 中间 右边去组成两组
    //好像也不对!不一定就是两次买入两次抛出
    //用贪心算法
    int res = 0;
    for(int i = 1; i < n; i ++)
    {
        int r = price[i + 1] - price[i];
        if(r > 0) res += r;
    }

    printf("%d", res);
    return 0;
}