从现实问题到计算机程序（Week 5）

总结回顾

计算机只能按照程序去执行，不可能自己“想出”一个解决问题的方法

面对一个问题，你必须自己找到解决方案，才有可能做出相应的程序

所以，没有解决方案的时候，不要急着动手写程序

• 切饼
  • 假设：有一张足够大的饼，有一把足够长的刀
  • 要求：每次切一刀
  • 问题：n刀最多能切出多少块饼
  • 结论：q（n）=q（n-1）+n ⬅️这个解决方案是计算机“想”不出来的

现有构想再写程序

问题➡️解决方案：思考

解决方案➡️程序：描述

在结构化程序设计中，总是按照“先粗后细，先抽象后具体“的办法，对索要描述的解决方案进行穷尽分解，知道分解为顺序、分支、循环三种结构

在写程序前，先构思好程序的结构，可以先写出程序轮廓，再后补变量定义等细节

事例

• 鸡兔同笼问题

  • 问题描述：一个笼子里面关了鸡和兔子，已知脚数a，问笼子里面至少有多少动物，至多有多少种动物

  • 输入&输出

    2➡️0 0

    3➡️0 0

    20➡️5 10

#include<iostream>

using namespace std;

int main()

{

  int nCases,i,nFeet;

  cin>>nCases;

  for(i=0;i<nCases;i++)

  {

    cin>>nFeet;

    if(nFeet%2!=0)

      cout<<"0 0"<<endl;

    else if(nFeet%4!=0)

      cout<<nFeet/4+1<<" "<<nFeet/2<<endl;

    ekse

      cout<<nFeet/4<<" "<<nFeet/2<<endl;

  }

  return 0;

}

• 百元买百鸡问题
  • 问题描述：假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在有100元要求买100只鸡，编程列出所有可能的购机方案。
  • 穷举法：将可能出现的各种情况一一测试，判断是否满足条件。

#include<iostream>

using namespace std;

int main()

{

  int x,y,z;

  cout<<"\t 母鸡\t\t 公鸡\t\t 小鸡"<<endl;

  for(x=0;x<=33;x++)

    for(y=0;y<=50;y++)

      for(z=0;z<=100;z++)

      {

        if((x+y+z)== 100)

          if((3*x+2*y+0.5*z)==100)

            cout<<"\t"<<x<<"\t\t"<<y<<"\t\t"<<z<<endl;

      }

  return 0;

}

//可简化一层循环：z=100-x-y

• 分出奇偶数
  • 问题描述：从键盘上输入10个整数，请将其中的奇数和偶数识别出来，分别放入不同的数组中并输出
  • 输入示例：23 34 65 43 67 12 67 341 61 34
  • 输出示例：
    • 奇数：23 65 43 67 67 341 61
    • 偶数：34 12 34

#include<iostream>

using namespace std;

int main()

{

  int all[10],odd[10],even[10];

  int i = 0; j = 0;

  for(; i<10; i++)

    cin>>all[i];

  int numOdd = 0;

  int numEven = 0;

  for(i = 0; i < 10; i++)

  {

    if(all[i] % 2 != 0)

    {

      odd[numOdd] = all[i];

      numOdd++;

    }

    else

    {

      even[numEven] = all[i];

      numEven++;

    }

  }

  for(i = 0;i < numOdd;i++)

    cout<<odd[i]<<" ";

  for(i = 0;i < numEven;i++)

    cout<<even[i]<<" ";

  return 0;

}

• 整数排序
  • 问题描述：从键盘上输入10个整数，请按照从大到小的顺序将他们排列好，并按新的次序输出到屏幕上
  • 输入示例：23 34 65 43 67 12 67 341 61 34
  • 输出示例：341 67 67 65 61 43 34 34 23 12
  • 选择排列：最简单的排列方式

#include<iostream>

using namespace std;

int main()

{

  int a[10];

  int i=0,j=0;

  int temp = 0;

  for(i = 0;i < 10; i++)

    cin>>a[i];

  for(i=0;i<0;i++)

    for(j=i+1;j<10;j++)

    {

      if(a[j]>a[i])

      {

        temp = a[i];

        a[i] = a[j];

        a[j] = temp;

      }

    }

  for(i = 0;i < 10; i++)

    cout<<a[i]<<" ";

  return 0;

}

• 整数奇偶排序

  • 问题描述：输入10个0～100之间的不同整数，彼此以空格分割重新排序以后输出（也按空格分割）

  • 要求：1.先输出其中的奇数，并按从大到小排列；

    ​ 2.然后输出其中的偶数，并按从小到大排列。

#include<iostream>

using namespace std;

int main()

{

  int all[10],odd[10],even[10];

  int i=0,j=0;

  for(; i<10;i++)

    cin>>all[i];

  int numOdd = 0;

  int numEven = 0;

  for(i = 0; I , 10; I++){

    if(all[i]%2 !=0)

    {

      odd[numOdd] = all[i];

      numOdd++;

    }

    else

    {

      even[numEven] = all[i];

      numEven++;

    }

  }

  for(i = 0; i<numOdd-1;i++){

    for(j = i;j<numOdd;j++)

    {

      if(odd[j]>odd[i])

      {

        int tmp = odd[i];

        odd[i] = odd[j];

        odd[j] = tmp;

      }

    }

  }

  for(i = 0; i < numEven - 1; i++)

  {

    for(j = i; j < numEven;j++)

    {

      if(even[j]<even[i])

      {

        int temp = even[j];

        even[j] = even[i];

        even[i] = temp;

      }

    }

  }

  for(i = 0; i < numOdd; i++)

    cout<<odd[i]<<" ";

  for(i = 0; i < numEVen; i++)

    cout<<even[i]<<" ";

  return 0;

}

结构化程序的基本思想

• 程序由若干个模块组成
• 模块之内高内聚
• 模块之间低耦合

作业题

Quiz 1 晶晶赴约会

#include <iostream>

using namespace std;

int main() {

    int a;

    cin >> a;

    if (a == 1 || a == 3 || a == 5)

        cout << "NO" << endl;

    else

        cout << "YES" << endl;

    return 0;

}

Quiz2 奇数求和

#include <iostream>

using namespace std;

int main() {

    int m, n, result = 0;

    cin >> m >> n;

    while (m <= n) {

        //对于m和n之间的每一个数， 如果它是奇数，那么就加入到我们的结果里。如果不是就跳过。

        if (m % 2 == 1)

            result += m;

        m++;

    }

    //最后输出

    cout << result << endl;

    return 0;

}

//更快算法：若m为奇数，则循环+2求和至大于等于n；若m为偶数，则先+1再循环+2求和至大于等于n

Quiz3 整数的个数

#include <iostream>

using namespace std;

int main(){

    int k;

    cin>>k;

    int n1=0, n5=0, n10=0;

    for (int i=0;i<k;i++){

        int n;

        cin>>n;

        if (n == 1) n1++;

        else if (n == 5) n5++;

        else if (n == 10) n10++;

    }

    cout<<n1<<endl;

    cout<<n5<<endl;

    cout<<n10<<endl;

    return 0;

}

Quiz4 1的个数

# include <iostream>

using namespace std;

int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {

        int x, ans = 0;

        cin >> x;

        while (x > 0) {

            ans += x % 2;

            x /= 2;

        }

        cout << ans << endl;

    }

    return 0;

}

//这道题的解法就是反复地除以2，看最低位是1还是0。

Quiz5 数组逆序重放

#include <iostream>

using namespace std;

int a[100];

int main() {

    int n;

    cin >> n;

    for (int i = 0; i<n; i++)

        cin >> a[i];

    while (n--) { //常用的倒序计数循环，等价于while(n-->0)

        cout << a[n];

        if (n > 0) cout << " "; //如果不是最后一个数那么就要用空格分隔开

    }

    return 0;

}

//顺序输入倒序输出，如果要求通过修改数组本身实现逆序重放,则使用临时变量temp，将首尾元素逐个交换即可。