体验编程之美 饮料供应问题

动态编程,贪婪算法,实际问题的建模过程

现实问题描述

  公司水房提供很多种类饮料,已经统计获得大家对每种饮料的满意程度;STC负责给公司提供饮料,每天的总容量为V,每种饮料的单个容量都是2的方幂,比如王老吉,都是2的三次方为8升的;STC的存货也是有限的,这会是每种饮料的购买量上限。统计数据中使用饮料名字,容量,数量,满意度来描述一中饮料,问如何保证最大的满意度啊。

问题建模

  我刚看到这道题目的时候,其实是很困惑的,完全不知道该如何下手。因为之前刷leetocde算法题目时,每个题目是使用编程域的语言进行描述的,比如:复制一个具有随机指针的链表。而这道题却是一个完全现实问题域描述,这样我们就需要进行建模,将这个实际问题转换为之前比较常见的算法问题。

  假设ST提供n种饮料,用(Si,Vi,Ci,Hi,Bi) (对应饮料的名字,容量,可能的最大数量,满意度,实际购买量)来标示第i中饮料,其中可能的最大数量指如果仅买这种饮料的可能最大数量,比如对第i种饮料,Ci=V/Vi;

  基于现实域的描述,我们有以下两个公式:

Read More
Share

西方文化和精神概述

    自由,契约,宪政,理性,博爱
    有些时候,我总会处于一种莫名的状态中:认定了要去一件事情,却总是在一天一天拖延下去,像是生活有太大的惯性,无法做出改变一样。
    想写下这篇文章很久啦,一直都没有动笔的勇气和时间。说没有勇气可能有点矫情,但只从大学以来,除了“感人至深”的入党申请书之外,无论是笔,或者键盘,我都没有让思想从我指尖流淌出去,固化成文章;说没有时间可能有点做作,显得自己很忙似的,但可能时间都花费到了其他地方去了吧?
    这个学期我选修了王雄老师的《西方文化和精神》课程,期间了解了整个西方文化精神的起源,发展,和形成的过程。对于工科生的我,实在是受到了太多的震撼!
    以下的观点多是来自我的课程笔记和一些记忆,如有错误,请多包含。
    开头当然要请出我们的马克思啦,马克思认为等到未来生产力高度发达了,无产阶级必然会夺取政权,获得解放。但是马克思过度夸大了阶级形成的外部因素,忽略了无产阶级意识的形成的重要性。一个阶级的自我意识是不会自动形成的,必然需要重大的事件或者人物去推动(不符合毛概欧),比如毛主席在第一次国共合作时主要推动的农民运动讲习所,就是要激发农民阶级的自我意识。
    那资产阶级的自我意识是如何形成的呢?
    西方资产阶级自我意识即西方文化和精神的发展过程大概为:古希腊古罗马阶段,中世纪基督教,文艺复兴,宗教改革,启蒙运动。从每个阶段中我们都可以提取出西方文化的一级词汇,也就是最能代表西方文化和精神的词汇,比如说启蒙运动宣扬的自由,理性,契约,宪政。
    我不会在这里过多的阐述这些阶段中所涌现的具体人物以及他们的思想,他们早已如同头顶星空一般,虽你不常仰头惊叹其浩瀚壮阔。
    我主要会讲很令人惊奇的思想。第一个是个人主义和集体主义的区别。这两个词不是好与坏的主义,而是两种不同的价值观,个人主义不等于自私,而是强调集体的存在在于保障个人的权益,而群体主义不用说,大家应该都感受到。一个比较典型的场景就是:一个村长,一心为了村民,希望大家都变得富有,但是他总是大包大揽,喜欢自己把所有事情都管起来,他总是对大家说:你们不用管,你们不用管,我全部做的好好的给你们还不行吗?马克思也曾经说过:人类社会的自由和发展是由每个人的自由和发展为基础和前提的。这两种主义和自由主义还有群体功利主义也是有区别的,但是我也搞不清楚它们的区别。
     第二个是关于上帝是否存在的问题。这首先要从启蒙运动讲起啦,启蒙运动推崇理性,并且崇拜理性所带来的科学进步,社会发展。但是两次世界大战和近代社会人们关系的异化让人们开始反思理性。人之间关系的异化有很多的体现,比如卡夫卡的《变形计》,《城堡》。而且不仅人和人的关系异化了,人和机器的关系好像也改变了,从而导致双层的异化。机器本来是人类发明并用来帮助人类的,但现在人们好像是被机器约束了,而不是人来约束机器。卓别林的《摩登时代》和富士康事件可能都体现这个主题。好像还有一本不错的书专门讲述这个问题,叫做《单向度的人》那么人们是如何反思的呢?首先就是关于上帝是否存在的问题。人们认为宗教的思想是和理性思想完全不同的两种思维方式,宗教的思想是先验的,讲究天启和惯性思维,那么使用纯粹理性的思维去否定宗教的存在是否合理呢?好像是有点方枘圆凿。如果你使用纯粹的理性思维如何去证明上帝是不存在的呢?卡尔·波普尔好像也对此做出解释,他认为真理是可以被证伪的,无法被证伪的就不是真理,体现了对科学和非科学的区分啊。他还对马克思理论做个一个三段式推理,也是很有趣的。
    除了上边所说的人的异化,启蒙运动所标榜的真理蜕变了,高尚的价值理性蜕变成了工具理性,不在于追求知识和理性作为最高标准,而是追求效率和福利作为最高目标,但是提高了效率,人们自己的感受呢?
    第三个是关于中国文化的问题。首先中国的哲学中对于方法论的认识始终没有得到发展,始终处于一种神秘主义的阶段,比如说老子的“道可道,非常道”,还有禅宗的顿悟。他们都没有述说知识和思想的具体来源,并且认为有些知识不能写出来,只能自己领悟。这种哲学无疑对中国的科技发展产生了很大的影响。而在西方,无论是莎士比亚的《工具论》还是培根的《新工具》都给给出了获取知识和真理的可以循序的方法和道路。培根不经会写小短文,还是现代实验科学的奠基人啊!然后是我们对教育的理解,当然这是古代中国思想的体现,它强调老师到学生的继承,而缺乏反思性。而西方则相反,比如弗洛伊德的学生中反对他学说的两个学生最终都取得了巨大的成功。
    第四个是对于悲剧的理解。鲁迅说悲剧就是把有价值的东西毁灭给你看,那西方的观点呢?悲剧一般有三个层面,第一个是命运悲剧,代表性作品就是索罗克勒斯的《Antigon》和《Oedipus》.正真的悲剧不是对与错的争斗,比如《白毛女》,而是选择的悲剧,是好与好的争斗。比如《Antigon》;而《Oedipus》就是讲述杀父妻母的故事,这是一种人生的境遇,无论如何努力,都无法逃脱的命运,所以俄狄甫斯最后刺瞎双目,自我流放。第二等是性格悲剧,莎士比亚的悲剧都是如此,都是因由个人的性格所导致的悲剧,比如软弱的哈姆雷特;第三等就是社会悲剧,也就到了人与人的异化关系问题,比如《白毛女》,《雷雨》,《玩偶之家》。
    大概就这么多啦。

Share

体会编程之美,找出最大的k个数

 今日上课无事,偶尔看到《编程之美》的一道题目,如何找出n个数中的最大的k个数,不仅惊奇于其提供的多种解法,而且感叹其中很多解法都是之前的我们熟悉解法的变种。废话不多说,我们来依次看一下不同的解法和相应的分析

思路一

  1. 使用排序算法先对n个数进行排序,然后取最大的k个数。
  2. 先找出n个数中最大值,然后在找出n-1个数中的最大值,一直进行,知道找出k个数。

Read More
Share