本文主要是介绍算法笔记系列：4.3 递归 4.4 贪心，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法笔记系列：4.3 递归 4.4 贪心

• 4.3.1 分治
• 4.3.2 递归
• 4.4.1 简单贪心
• • • 【PAT B1020】
    • 【PAT B1023】

4.3.1 分治

将原问题划分为若干个规模较小而结构与原问题相同或相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到为原问题的解

4.3.2 递归

递归逻辑中两个重要的概念：递归边界，递归式

• Fibonacci数列的第n项

  # include<cstdio>
  int F(int n){
      if (n==0||n==1) return 1;
      else return F(n-1)+F(n-2);
  }
  int main(){
      int n;
      scanf("%d",&n);
      printf("%d\n",F(n));
      return 0;
  }
  

• 全排列

  # include<cstdio>
  int n;
  int p[10000];
  bool flag[11]={false};
  
  void generateP(int index){
      if (index==n+1){
          for (int i=1;i<=n;i++){
              printf("%d",p[i]);
          }
          printf("\n");
      }
      for (int m=1;m<=n;m++){
          if (flag[m]==false) {
              p[index]=m;
              flag[m]=true;
              generateP(index+1);
              flag[m]=false;
          }
  
      }
  }
  int main(){
      n=3;
      generateP(1);
      return 0;
  }
  

4.4.1 简单贪心

总是考虑当前状态下的局部最优，来使全局的结果达到最优

【PAT B1020】

# include<cstdio>
# include<algorithm>
using namespace std;
struct mooncake{
    double store;
    double sell;
    double price;
}cake[1010];

bool cmp(mooncake a,mooncake b ){
    return a.price>b.price;
}

int main(){
    int N;
    double D;
    scanf("%d %lf",&N,&D);
    for (int i=0;i<N;i++){
        scanf("%lf",&cake[i].store);
    }
    for (int i=0;i<N;i++){
        scanf("%lf",&cake[i].sell);
        cake[i].price=cake[i].sell/cake[i].store;
    }
    sort(cake,cake+N,cmp);
    double ans;
    for (int i=0;i<N;i++){
        if (cake[i].store<=D){
            D-=cake[i].store;
            ans+=cake[i].sell;
        }else{
            ans+=cake[i].price*D;
            break;
        }
    }
    printf("%.2f",ans);
    return 0;
}

【PAT B1023】

# include<cstdio>
int main(){
    int count[10]={0};
    int n;
    for (int i=0;i<10;i++){
        scanf("%d",&n);
        count[i]=n;
    }
    for (int i=1;i<10;i++){
        if (count[i]!=0){
            printf("%d",i);
            count[i]--;
            break;
        } 
    }
    for (int i=0;i<10;i++){
        for (int m=0;m<count[i];m++){
            printf("%d",i);
        }
    }
    return 0;
}

这篇关于算法笔记系列：4.3 递归 4.4 贪心的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！