« 上一篇下一篇 »

大学需要发散的思维

       首先先祝贺新一届的新生,你们熬过了煎熬的高中生活,又即将要结束大学的第一道考验——军训。很快,你们就要加入大学生的上课队伍了!是不是很激动呢?

      咦?先别激动哦!你是计算机专业的新生,你真的准备好对这门专业的学习了吗?哦?你说你高中是选考技术的,一定没问题?!

      是吗?那我们拿题目说话,先来3道测试题,看看你能答的怎么样吧!


      问题一:

             有一组数,数字的个数不确定,可能是10个也可能是10万个甚至10亿个,但是这些数字的总和不会超过double类型的范围。这些数字由键盘输入,输入-1时表示数据输入结束。请问怎样求这些数的平均值?


      问题二:

             有一组数,数字的个数不确定,但是至少有10万个,由键盘输入,输入#结束。每个数字的范围在[0,500]内的整数,请问有什么办法不对这些数进行排序,求出其中的中位数?


      问题三:

             有两个整数变量x,y。能不能不借助其他变量,也不开辟新的内存,直接交换这两个变量的值?


      我将这三个问题依次发给3位我们学校的大一计算机专业的新生做,考察的结果是,1位没有通过挑战,直接放弃了。1位在提示下做对了第一题,无提示做出了第三题,没有做出第二题。最后一位,在提示下做出了第一、第二题,没有做出第三题。

      我们来分析一下:

      第一题,基本上他们的思路都是先创建一个数组,把这些输入的数都存起来,然后累加后再除以个数,得到最后的平均数。咳咳,问题来了!这题的重点是,输入的数的规模是不确定的啊!你要创建数组,你怎么知道要开辟多大的数组呢?数组的元素是多少个?数的个数可以达到10亿这个数量级,内存够用吗?因为,这一招是不行的!于是,我给他们提示,我们只需要3个变量即可解决这个问题!我们求的仅仅是平均数,不做其他事情啊!很快,2位同学想到了新的方案:3个变量,sum记录所有输入的数的和,count记录输入的数的个数,temp用于临时存取输入的数。来个while循环,输入一个数马上加入sum,count++同时累计个数,最后sum/count,不就得到答案了吗?超简单!代码如下:

int main()

{

 int temp, count = 0;

 double sum = 0.0;

 scanf("%d", &temp);

 while (temp!=-1)

 {

  sum += temp;

  count++;

  scanf("%d", &temp);

 }

 printf("The average is %f\n", sum / count);

 return 0;

}

       从这道题中可以看出我们的同学有点思维定势,我求的是平均数,平均数是什么?就是这些数的和再除以个数。我只需要得到两个东西,一个是和一个是个数。那么我为什么不能变输入边累计呢?为什么一定要保存这些输入的数进入内存呢?这些都不需要。小规模的问题可能没什么差距,但是问题规模一大,这种先全部录入内存的思路就不行了。


       我测试的同学中,没有人自己回答出问题二,不知道现在看到的你想到答案了没有。有的甚至直接回答答案是250...大哥,这是中位数啊,万一我输入的数里面就没有250呢?这个答案肯定错的啊!我们要正确求出中位数啊!

       还是那个老原因,求中位数离不开排序,思路就是往排序那边看。不排序我就不知道要怎么求中位数了。规模小还没事,我内存存的下,排序也不会花很多时间。然而,这个问题的规模很大哦!存不下内存中,哪怕真的用排序,这个时间复杂度也是很高的!我们要这样思考问题,求中位数需要怎么求?我们只需要知道这组数据的个数,将个数/2得到的这个数,就是中位数所在的位置!当然不能排序!不能排序却要知道第count/2这个位置的数是谁,怎么办?我们看看题目的条件,已知所有的数都是[0,500]内的整数啊!说明取值只有501种可能,那我们可以定义一个数组a[501],这个是完全可以的!然后这个数组用于统计0~500这501个整数分别出现的个数!没问题吧!我输入一个数,如果是3那就a[3]++,如果是50那就a[50]++,输入一个的同时count++来统计数据的个数。等我输入完毕后,我就知道数据的个数,也知道0~500每个数出现的次数了。那好,我也知道中位数是排第几的数了!从a[0]开始数,加上a[1]加上a[2]一直往后面加,直到加到a[x]的时候发现这个和超过了或等于count/2,那就说明中位数是x了!因为count/2落在了这里面啊!上代码!

#include<stdio.h>
int main()
{
 int i, j, count = 0, pos, sum = 0;
 int a[501] = { 0 };
 printf("开始统计!\n");
 /*输入部分略*/
 printf("统计完毕!\n");
 if (count % 2 == 0)
  pos = count / 2;
 else
  pos = count / 2 + 1;
 printf("中位数的位置在%d\n", pos);
 for (i = 0; i < 501; i++)
 {
  if (pos >= sum && pos <= sum + a[i])
  {
   printf("中位数为%d\n", i);
   break;
  }
  sum += a[i];
 }
 return 0;
}

       利用统计的思维!利用数组的下标!不妨是一个好思路。


       问题三,看起来很简单,如果没有那个新变量限制的条件的话,答案就是t = x;x = y;y = t;相当于3个空杯子,2杯水倒来倒去进行交换。不过没有其他变量,仅靠对x,y进行加加减减的操作也可以实现!

x = x + y;
y = x - y;
x = x - y;

       怎么样,自习再琢磨琢磨?是不是可行呀!虽然也是进行了3次运算,但是我们还是节省了内存了呀!


       不管你上面的题目有没有独立思考出正确的答案,总之还是希望即将开始大学计算机专业学习的你要懂得发散思维,要经常去思考算法这方面的问题!只有这样多想多思考,才能让思路越来越灵活,才能更好地解决更多的更复杂的问题!