[音乐播放] 教授：好的。 这是CS50，这是 三星期结束。 所以，我们今天在这里，而不是在桑德斯 剧场，而是在韦德纳图书馆。 其内部是一个工作室 被称为豪瑟工作室， 或者我们应该说工作室H，或应 我们say--如果你喜欢这个笑话， 它实际上是从 同学，马克，网上， 谁通过Twitter提出之多。 现在，有什么很酷 是在工作室在这里 是，我被这些绿色包围 墙，绿屏或色度， 可以这么说，这意味着，CS50的 制作团队，我并不知道 现在，可以把 我最在世界任何地方， 是好还是坏。 现在是什么样的未来，问题集 二是在你的手中本周， 但问题集 三此接下来的一周， 你将受到挑战 所谓游戏的15 一个老党员赞成票 你可能还记得接受 作为一个孩子，有一大堆 可滑动的上，下的数字， 左，右，以及有一个缺口 在拼图，您在其中 实际上可以滑动的拼图。 最终你收到此 拼图一些半随机的顺序， 和目标是 顶级排序，到下， 从左到右，从一个 一路攀升至15。 不幸的是，实施 你手边 将是软件 根据，不是身体。 你实际上将不得不写 代码与学生或用户可以 打15场比赛。 而事实上，在黑客 游戏的15版， 你会是一个挑战来实现， 这种老派的不只是播放 游戏，而是求解 这一点，实现上帝模式， 可以这么说，实际上 解决这一难题的人， 向他们提供线索， 提示后，在提示。 因此，更多的在下周。 但是，这是什么样的未来。 现在还记得，在本周早些时候 我们有这个悬念，如果你愿意， 因此，我们正在做排序的最好 明智的是一个上限的大O的n 平方。 换句话说，冒泡排序， 选择排序，插入排序， 所有的人，而不同 在执行过程中， 演化成一个n平方运行 时间在非常最坏情况。 而我们通常认为 最糟糕的情况下进行排序 是一个你投入 是完全倒退。 事实上，花了相当多的步骤 要实现每个算法。 现在，在类的尽头 回想一下，我们比较冒泡排序 反对对另外一个选择排序 我们称之为合并排序的时候， 我建议它采取 优势从一周一节课 零，分而治之。 并以某种方式达成某种 对数运行时间最终， 而不是东西 这是纯粹的二次。 而且它不是相当的对数， 这是多一点比。 但是，如果你从类回忆， 这是更多，更快。 让我们来看看，我们不放过​​。 冒泡排序与选择 排序与归并排序。 现在，他们都在运行，在 理论上讲，在同一时间。 CPU被以相同的速度运行。 但是你能感觉到有多无聊本 是很快将成为， 并有多快，当我们注入 有点星期零的算法， 我们可以加快速度。 所以标记排序看起来令人惊讶。 我们怎样才能利用它，为了 更快速的数字进行排序。 好吧，让我们回想起 一个成分，我们 有回零一周，那 在电话簿中寻觅， 并且记得， 伪代码，我们建议， 通过它我们可以找到 有人喜欢迈克·史密斯， 看起来有点这样的事情。 现在来具体看看 在第7行和8，以及10和11， 这导致该循环，因此我们维持 回到第3行一次，又一次， 然后再次。 但事实证明，我们可以查看 这种算法，这里在伪代码中， 一点更全面。 事实上，我在寻找什么 在这里，屏幕上， 是一种算法，用于搜索 迈克·史密斯在一些组页面。 事实上，我们可以简化 算法在这些线路7和8， 而10和11，只是这么一说， 我在这里介绍了黄色。 换句话说，如果麦克 史密斯早在书中， 我们并不需要指定步骤 一步现在怎么去找他。 我们没有指定 回到3号线， 我们为什么不只是代替， 比方说，更一般地， 搜索麦克在 书的左半边。 相反，如果麦克 实际上后来在书中， 为什么我们不只是引用引文结束搜索 麦克在书中的右半部分。 换句话说，我们为什么不只是 排序撑船对自己说， 搜索麦克在这 书的一部分， 并把它留给我们现有的 算法告诉我们 如何在搜索麦克 即左书的一半。 换句话说，我们的 算法的工作无论是 电话簿该厚度的，这 厚度，或者任何任何厚度。 因此，我们可以递归 定义这个算法。 换句话说，对 屏幕这里，是一个算法 为寻找麦克·史密斯 之间的电话簿的网页。 因此，在管线7和10所示，让我们 只说这一点。 我用这个词了一下 以前，而事实上，递归 是的流行语现在， 和它的这个过程 做一些周期性通过某种方式的 使用您已有的代码， 并再次调用它， 又一次，又一次。 现在，这将是重要的 我们莫名其妙地底 出来了，不这样做无限长。 否则，我们将 有确实是一个无限循环。 但是让我们看看我们是否能借这个想法 递归的，又做什么 一次又一次，来解决 通过合并排序问题 排序，更加有效。 所以，我给你归并排序。 让我们一起来看看。 因此，这里是伪代码，用 这是我们可以实现分选， 采用这种算法称为归并排序。 这是相当简单，就是。 在n个元素的输入， 换句话说，如果你 给定n个元素和数字 字母或任何输入是， 如果你给定的n个元素，如果 n小于2，只是返回。 对？ 因为，如果n小于2，即 意味着我的元素列表 可以是0或1号，并 在这两个琐碎的情况下， 名单已经排序。 如果没有清单，它的排序。 而且如果有长度的列表 1，这显然排序。 所以该算法仅需要 真正做一些有趣的事情， 如果我们有两个或更多的 元素给我们。 因此，让我们来看看神奇的话。 元件的左半其他排序， 然后排序元素的右半 然后合并排序半。 什么样的心态弯曲 在这里，是，我真的不 似乎已经告诉过你 任何事情，只是还没有，对不对？ 所有我已经说过了，给定名单 n个元素，排序的左半边， 然后右半，然后 合并排序的一半， 但如果是实际的秘密武器？ 哪里的算法？ 那么事实证明，这两条线 首先，要素排序左前卫， 和排序右半元件， 是递归调用，可以这么说。 毕竟，在这个 时间点上，我必须 一种算法，用以 排序一大堆的元素？ 是。 就是这里。 这是就在屏幕上，并 这样我就可以使用同一套步骤 在左半排序， 我可以右半部分。 事实上，一次，又一次。 因此，好歹，我们将很快 看到这种情况，归并排序的魔力 嵌入在非常最终 线，合并排序的半部。 而这似乎相当直观。 你把两半，而你， 不知何故，把它们合并起来， 我们将看到这个 具体在某一时刻。 但是，这是一个完整的算法。 而让我们看看究竟为什么。 那么假设我们给这些相同 八种元素在这里在屏幕上，人们 通过八个，但他们 在看似随机的顺序。 而这一目标的手 这些元素进行排序。 嗯，我怎么能去 做它用，再次， 归并排序，按本伪？ 再次，这种根深蒂固的 你的头脑，就一下。 第一种情况是相当 琐碎，如果它小于2， 刚回来，没有工作要做。 所以真的有只有三个 步骤要真正记住。 又一次，又一次，我 会希望有 在左半排序， 排序的右半 然后一旦其 两个半部进行排序， 我想将它们合并在一起 成一个排序列表。 所以记住这一点。 因此，这里的原始列表。 让我们把这个作为 阵列，因为我们开始 两个星期，这是一个 连续的内存块。 在这种情况下，含有8 数字，背靠背回来。 而且，我们现在申请归并排序。 所以，我首先想要排序 这个列表的左边一半， 让我们，因此， 集中4,8，6和2上。 现在，我怎么去 分拣大小4的名单？ 嗯，我必须现在考虑 排序的左半的左侧。 再次，让我们倒带只是一瞬间。 如果伪代码是这样的， 而我给八素， 8显然是更大 大于或等于2。 因此，与第一种情况下不适用。 因此，八个元素进行排序，我第一次 排序元件的左半部， 接着我的右半边，然后我合并 两个半排序，每个大小为4。 行。 但如果你只是告诉我，排序 左半部分，也就是现在的大小为4， 我怎么排序的左半边？ 好吧，如果我有一个 四个要素投入， 我第一次排序的左 二，则对二， 然后我把它们合并起来。 如此反复，就显得有点 一记弯曲在这里比赛， 那种因为你，要 还记得你在哪里的故事， 但在一天结束时， 给定任意数量的元素， 你首先要排序的 左半，然后右半边， 然后把它们合并起来。 让我们开始这样做。 以下是八种元素的输入。 现在，我们正在寻找的左半部分在这里。 我怎么排序四个要素？ 嗯，我第一次排序的左半边。 现在，我怎么排序的左半边？ 嗯，我一直在给定的两个元素。 因此，让我们这两个元素进行排序。 图2是大于或 等于2，当然。 所以这第一种情况下不适用。 所以，我现在有向左排序 上半年这两个元素。 左半部分，当然​​，仅仅是4。 所以，我怎么排序一个元素的列表？ 现在好了，特别的基本情况 往上顶，可以这么说，适用。 1小于2，和我的 名单确实是大小为1。 所以我就回来。 我没有做任何事情。 事实上，看看我有 完成后，4已经排序。 就像我已经 部分成功在这里。 现在看来很愚蠢 权利要求，但它是真实的。 图4是尺寸1的列表。 它已经排序。 这是左半部。 现在我排序的右半​​部分。 我的输入是一个元素，8 同样，已经排序。 愚蠢，太，但同样， 这一基本原则 将会让我们现在建 在此之上成功。 4排序，8排序，现在 什么是最后一步？ 因此第三和最后的步骤，任何 一次你排序列表，召回， 是要合并的两半， 左和右。 因此，让我们这样做。 我的左半边，当然，4。 我的右半边是8。 因此，让我们做到这一点。 首先我要分配 一些额外的内存， 我将在这里代表， 因为只是一个辅助阵列， 这是足够大，以适应这一点。 但是，你能想象延伸 该矩形的整个长度， 如果我们需要更长时间之后。 我如何采取4和8，和合并 尺寸1在一起的那两个名单？ 在这里，也很简单。 4是第一位的，然后是8。 因为如果我要排序的 左半，然后右半边， 然后合并这两个半 同时，在有序， 4是第一位的，然后是8。 因此，我们似乎正在取得进展，甚至 虽然我没有做任何实际工作。 但是，请记住，我们是在故事中。 我们最初采取了八大要素。 我们的排序左半，这是4。 然后，我们整理了左半 的左半部分，为2。 在这里，我们走了。 我们正在与该步骤完成。 因此，如果我们排序 左半边的2，现在我们 得的2右半排序。 这样的2的右半边是 这里这两个值，6和2。 因此，让我们现在就采取大小的输入 2，和排序左半，然后 右半，然后 把它们合并起来。 那么我怎么排序大小的列表 1，仅包含数6？ 我已经做了。 大小为1的那个列表进行排序。 我如何排序的另一个列表 尺寸如图1所示，所谓的右半。 那么它也已经排序。 数字2是孤独的。 所以，现在我有两个半，左， 好吧，我需要将它们合并在一起。 让我给自己做一些额外的空间。 并把2在那里， 然后在那里6，从而 排序该列表，左，右， 和合并在一起，最终。 所以，我在稍微好一点的形状。 我不这样做，是因为清楚4，8，2， 6是不是我想要的最终排序。 但是我现在有2号两个列表，该 双方都分别进行了排序。 所以，现在，如果你在你的心中的倒带 眼睛，哪里是离开我们？ 我开始与八素，然后我 又缩减到了4左半部分， 然后2左半，和 然后为2的右半边， 我完成了，因此，左排序 一半的2，以及2的右半 那么什么是第三次，也是最后一步吗？ 我必须合并到一起 2号两个列表。 因此，让我们继续前进。 在这里，在屏幕上，给 我一些额外的内存， 虽然在技术上，注意，我 有一大堆的空白向上顶 那里。 如果我想特别 有效的空间明智的， 我刚开始运动的元素 来回，顶部和底部。 但只是为了视觉清晰， 我打算把它放在楼下， 让事情变得非常干净。 所以，我有大小2的两个列表。 第一个列表有4个和8个。 第二个列表中有2和6。 让我们合并这些 一起排序顺序。 当然，2，是第一位的， 然后4，然后6，然后8。 而现在，我们似乎越来越 有趣的地方。 的现在，我已经来分类的一半 列出，而巧合的是，这是 所有的偶数，但 确实是，只是一个巧合。 而我现在已经整理左 一半，所以，它的2，4，6，和8。 没有什么是坏了。 那感觉就像进展。 现在感觉我已经 在讨论永远的现在， 所以剩下，如果这待观察 算法确实是更有效的。 但是，我们正在经历 它的超级有条不紊。 当然，一台电脑，， 会做这样的。 因此，我们在哪里？ 我们开始与八个元素。 我排序的4左半部。 我似乎与完成。 所以，现在的下一个步骤是 排序的4的右半部分。 而这一部分，我们可以去 通过多一点 很快，虽然你 欢迎后退或暂停，只是 想通过它在 自己的节奏，但什么 我们现在是一个机会， 做同样的算法在四个 不同的号码。 因此，让我们继续前进，并专注于 右半部分，我们在这里。 的那左半 右前卫，现在的 左侧的左半边 一半的右半部， 以及如何排序大小的列表 1只包含数字1？ 它已经完成。 我该怎么做相同的列表 中只包含7尺寸1？ 它已经完成。 步骤三本半，然后 被合并这两个元件 成大小为2,1和7的一个新的列表。 似乎没有所做的一切 那么多有趣的工作。 让我们看看接下来会发生什么。 我只是排序的左半 我原来输入的右半部分。 现在让我们来排序的权利 半，它包含5和3。 让我们再次看一下左边 上半年，分类，右半边，排序， 并合并这两个在一起， 到了一些额外的空间， 3是第一位的，然后是5。 所以，现在，我们已经整理了 右半部分左半 原问题的，并 右边一半的右边一半 的原始问题。 什么是第三步也是最后一步？ 那么这两个半融合在一起。 因此，让我得到我自己的一些 额外的空间，但同样，我 可以使用备用空间往上顶。 但是，我们要保持 它简单直观。 让我在现在1合并，并 然后3，然后5，然后7。 现在，从而留下了我的 原问题的右半 这是完全排序。 那么剩下？ 我觉得我一直在说的 同样的事情又一次，又一次， 但是这反映了 事实是，我们正在使用递归。 使用的方法 算法再次，并再次， 对较小的子集 原来的问题。 所以，我现在有一个左排序 原来的一半问题。 我有一个正确排序的一半 的原始问题。 什么是第三个也是最后一步？ 哦，这是合并。 因此，让我们做到这一点。 让我们来分配一些额外的 记忆，但我的上帝，我们 可以把它的任何地方了。 我们提供这么大的空间 给我们，但我们会保持它的简单。 而不是回去和 第四我们原来的记忆， 我们只能这样做 视觉这儿下面， 完成了合并 左半和右半部分。 因此，通过合并，请问我需要做什么？ 我想借此元素的顺序。 所以看左半边， 我看到的第一个数字是2。 看看我的右半边， 我看到的第一个号码 是1，所以很明显这 一些做我想剜出， 并把第一个在我的最后名单？ 当然，1。 现在我要问同样的问题。 在左前卫，我已经 仍然得到了2号。 在右半， 我已经得到了3号。 哪一个我想选择？ 当然，数字2和 现在通知考生 是4上的右左，3。 让我们，当然，选择3。 现在的候选人4 右侧的左，5。 我们，当然，选择4。 6上右侧的左，5。 我们，当然，选择5。 6上右侧的左，7。 我们选择6，然后我们 选择7，然后我们选择8。 瞧。 话那么一个庞大的数字之后，我们 已经整理了八种元素列表 成一个通过八个列表， 它将与每一步增加， 但多少时间 它带我们去做到这一点。 嗯，我特意 奠定了东西出来形象化 在这里，让我们可以种 看到或体会到师 征服一个已经发生的事情。 事实上，如果你回头看看之后， 我已经离开所有这些虚线 在占位符，就可以了， 样的，看到的，以相反的顺序， 样的，如果你回头看的 现在的历史，我原来的名单 是大小8，当然，。 然后以前，我是 处理规模4的两个列表， 然后大小为2的四个列表， 然后大小为1的八个列表。 那么，这， 样的，提醒你？ 嗯，事实上，任何 我们已经算法 看着迄今我们 鸿沟和差距，并且差距， 再次保持有东西， 再次，结果在这个总体思路。 所以有什么东西 对数回事。 而且这不是n相当日志，但 有一个对数组件 ，这是我们刚刚做。 现在，让我们来考虑，实际上是如何。 所以日志N的，又是 一个伟大的运行时间， 当我们不喜欢的东西 二进制搜索，因为我们现在称呼它， 分而治之的策略 通过我们找到迈克·史密斯。 现在技术上。 这是n个日志基地2个，甚至 尽管大多数数学课， 通常10是你假设的基础。 但计算机科学家几乎总是 思考和谈论的基地2个方面， 所以我们一般只说日志 而不是n日志基地2 N， 但他们只有一个与 在计算机的世界一样 科学，顺便说一句， 有一个常数因子 两者之间的差别，因此它的 反正没有实际意义，更多的正式理由。 但现在，我们关心 大约是这样的例子。 因此，让我们不由的例子证明，但 至少使用数字的一个例子 手头作为一个全面的检查，如果你愿意。 所以以前的公式是日志基地 2 n个，但什么是正在这种情况下。 我有N个原始号码，或8 原有的一些具体。 现在，它已经有点 一段时间，但我敢 确保日志基地2 值8是3， 而事实上，有什么好的关于这是 该图3是次完全数 你可以将一个列表 又一次，又一次的长度为8， 又一次，直到你离开 只有大小为1的列表。 对？ 8变为4，进到2， 变为1，这是 反光正是中 图片我们有刚才。 那么一点点神智检查到哪里 对数是实际参与。 所以，现在，还有什么是这里涉及？ ñ。 所以请注意，每 一次我分裂名单， 尽管以相反的顺序历史 在这里，我还在做ñ的事情。 要求合并的步骤， 我接触的每一个数字， 为了将其滑入 其适当的位置。 因此，即使这个高度 图为大小日志N或3的n个， 具体地，换言之， 我做了三个部门在这里。 我没有多少工作要做水平 沿着这个图表每一​​次？ 好吧，我做了n步的 工作，因为如果我 有四个元素和四个元素， 我需要将它们合并在一起。 我需要经过 这四个和这四个， 最终合并它们 回八素。 相反，如果我有八手指 在这里，我不这样做，八 fingers-- sorry--如果我 有四个手指在这里， 这是我做的，四根手指 在这里，这是我做的， 那么这同样 像以前的例子，如果我做 有八个手指虽然 总的来说，我可以，那种，做的。 我可以准确地在这里做， 那么我可以肯定 合并所有这些名单 尺寸1在一起。 不过，我当然要看看 在每个元素一次。 所以该方法的高度是log N， 这个过程的宽度，可以这么说， 为n，所以，我们似乎 有，最终，是 大小n次的运行时间n记录。 换句话说，我们将 列表，记录了n次， 但我们做到了每一次，我们有 触摸的每一个元素 为了将它们合并 总之，这 为：N步，所以我们有n次日志N， 或者作为一个计算机科学家会说， 渐近，这 将是很大的字 来描述的上 势必在运行的时候， 我们正处在一个大O运行 日志N次的，可以这么说。 现在，这是显著的，因为 回顾一下运行时间分别为 与冒泡排序和选择 排序和插入排序， 甚至有几个人的存在， Ñ​​平方是我们在那里的。 你也可以，那种，看到这个在这里。 如果n的平方显然是n倍 N，但在这里我们有N次登录N， 我们已经知道，从周 零，即日志n时，对数， 是不是一些线性好。 毕竟，回忆图片 与红色和黄色的 而绿线，我们画的 绿色对数线要低得多。 因此，更好更快 比直黄色和红色的线， n次N日志，着实更好 比n次N，或N的平方。 因此，我们似乎有 识别算法合并 那种运行在多 更快的时间，而事实上， 这就是为什么，在本周早些时候，当 我们看到泡沫之间的较量 排序，选择排序，并合并 排序，归并排序真的，真的赢了。 事实上，我们甚至没有等待 对于冒泡排序和选择排序 去完成。 现在让我们来一个其他通 在此，从一个稍微更 正式的角度来看，只要在 情况下，这种共振效果更佳 高于层面的讨论。 因此，这里的算法了。 让我们扪心自问， 什么的运行时间 是这个算法的各个步骤？ 让我们把它分为第一 壳体和第二壳体。 中频和ELSE在IF的情况下， 如果n小于2时，只返回。 感觉像固定时间。 这是，那种，像两个步骤， 如果n小于2时，然后返回。 但是，正如我们周一表示， 固定时间，或大O 1， 可以是两个步骤，三 步骤，甚至是1000步。 重要的是，它的 的步骤的数目恒定。 因此，黄色高亮伪 在这里试车时，我们会打电话给它， 恒定的时间。 所以更正式，和 我们将用于：此 将在多大程度上我们 正式这种权利now-- n个T， 一问题的运行时间 这占据N出头作为输入， 等于大O之一， 如果n小于2。 因此，它是有条件的。 所以要清楚，如果n小于 2，我们有一个很短的列表，然后 的运行时间，T的n，其中n是 1或0，在这种非常具体的情况下， 它只是将是恒定的时间。 这将需要一个 一步，两步，等等。 它是一个固定的步数。 因此，多汁的部分肯定是在 在伪另一种情况。 该ELSE情况。 排序左元素的一半，排序权 半元件，合并排序的半部。 多久每一这些步骤走？ 好吧，如果运行 时间到n个元素进行排序 是，我们很叫它 一般，n个T， 然后左排序 一半的元素 一种是，好像是说， ñ对T除以2， 并且类似地排序的右半 因素之一是，那种，好像说， n个牛逼分2，然后 合并排序的一半。 那么，如果我有一些 元件的数目在这里， 样四，有的数 这里的元素，如4， 我必须合并这四个中 在，并在各一个的这四个 后等，从而使 最终我有八个元素。 这感觉就像那是大O n个步骤？ 如果我有n个指和各 它们已被合并到的地方， 这是像另一个n步。 因此，我们确实通过公式， 我们可以表达这一点， 虽然有点scarily在第一 一目了然，但它是 捕捉正是这样的逻辑。 T N的运行时间，如果n 是大于或等于2。 在这种情况下，在ELSE情况下，是正对T 除以2的n个除以2，再加上T， 再加上大O n的一些 步线数， 也许正是N，也许2倍 N，但它的大概，n阶。 所以这也就是我们如何 通过公式表达这一点。 现在，你不会不知道这一点，除非 你已经记录了它在你的心中， 或看它在 背课本，那 可能有一点 备忘单底， 但这是，事实上，将要 给我们一个大O的n log n个， 因为复发了 你现在看到的在屏幕上， 如果你真的做到了出来，用 无限多的例子， 或者你通过公式做了，你会 看到这一点，因为此公式 本身是递归的，与叔 ñ过的东西就没事了， 并在左边ñ超过T，这样可以 实际上被表达，最终 的n log n个大去了。 如果不相信，这是 精细现在，只要 采取的信念，那这就是，的确， 什么复发导致， 但是这仅仅是多了一个有点 数学方法寻找 在合并排序的运行时间 根据它的伪孤独。 现在，让我们有点 从所有这一切歇口气， 看一看在 某些前参议员，谁 可能看起来有点眼熟， 谁坐下来与谷歌的埃里克 施密特，前一段时间，接受采访 在舞台上，在一大堆的前面 人，谈话最终约 一个话题，那是相当熟悉的现在。 让我们一起来看看。 埃里克·施密特：现在参议员， 你在这里在谷歌， 我喜欢想的 总统作为一个工作面试。 现在很难找到一份工作作为总统。 奥巴马：对。 埃里克·施密特：你是 该怎么办[听不清]现在。 它也很难找到工作，在谷歌。 奥巴马：对。 埃里克·施密特：我们有疑问， 我们要求我们的候选人的问题， 而这一次是从拉里·施维默。 奥巴马：好。 埃里克·施密特：什么？ 你们以为我在开玩笑？ 就是这里。 什么是最有效的方式来 排序一百万的32位整数？ 奥巴马总统：Well-- 埃里克·施密特：有时候， 也许我很抱歉，maybe-- 奥巴马总统：不，不， 不，不，不，我think-- 埃里克·施密特：这不是它 - 奥巴马总统：我 想想，我觉得泡沫 排序将是错误的路要走。 埃里克·施密特：来吧。 谁告诉他的？ 行。 我没有计算机科学on-- 奥巴马：我们已经 得到了在那里我们的间谍。 教授：好的。 让我们后面现在离开 算法理论界 在渐近分析 物，并返回到某些主题 从周零和一，并开始 除去一些辅助轮， 如果你愿意。 让你真正了解 最终从地上爬了起来，什么是 怎么回事引擎盖下，当你 编写，编译和执行程序。 特别记得，这是 第一个C程序中，我们看了一下， 一个典型的，简单的程序 不爽，相对来说， 其中，它打印，你好世界。 而回想一下，我说，这个过程 该源代码经过 也正是这一点。 你把你的源代码，通过 它通过一个编译器，像锵， 进出自带目标代码，那 可能是这样的，零和的 计算机的CPU，中央 处理单元或脑， 最终可以理解的。 事实证明，这是一个 过于简单的一点， 我们现在正处在一个 位置梳理出 要了解什么是真正被 怎么回事引擎盖下 每次运行时间 铛，或更一般地， 每次你犯了一个程序， 使用make和CF 50 IDE。 尤其是，这样的东西 这首先产生， 当你第一次编译程序。 换句话说，当 把你的源代码 并编译它，什么是第一 被输出由锵 是一些被称为汇编代码。 而事实上，它看起来完全一样。 我在跑的命令 命令行前面。 铛破折号大写字母S的hello.c， 这个创建的文件 我叫hello.s， 这里面都是一模一样 这些内容，而多了几分 上述多一点的下方， 但我已经把最丰厚 这里，屏幕上的信息。 如果你仔细观察，你会看到 至少有几个熟悉的关键字。 我们主要在顶部。 我们在中间的printf下来。 而且我们也有世界你好 反斜杠N的报价楼下。 和其他一切在这里 是非常低的水平指示 计算机的CPU可以理解的。 该移动存储CPU指令 各地，从内存中加载的字符串， 最终，打印 事情在屏幕上。 现在发生什么事虽历经 此汇编代码生成的？ 最终，你这样做，事实上， 还是生成目标代码。 但步骤都是真正 已经持续引擎盖下 看起来有点像这样。 源代码变得汇编代码， 然后变成目标代码， 这里的工作的话是， 当您编译源代码， 走出来的汇编代码，然后 当你组装你的汇编代码， 出来自目标代码。 现在锵是超级复杂， 像很多的编译器， 而且它所有这些步骤 在一起，它不一定 输出任何中间 文件，您甚至可以看到。 它只是编译的东西， 这是一般术语，其 描述了整个过程。 但是，如果你真的想 要特别地，有 多了很多事也有。 但是，让我们现在也考虑，即使 该超级简单的程序，hello.c中， 叫的功能。 它呼吁printf的。 但我没写printf的，事实上， 随C，可以这么说。 这是一个函数调用这 在标准io.h，宣称这 是一个头文件，它 是一个主题，我们将实际 深入到更深入没多久。 但是，一个头文件 通常伴随着 由一个代码文件，源代码文件，所以 就像存在标准io.h. 不久以前，一个人， 或某人，也写 一个称为标准io.c中，在文件 它的实际定义， 或printf的实现， 和其他功能束， 实际上写的。 因此考虑到，如果我们考虑有 这里在左边，hello.c中，当 编译后，给了我们hello.s，即使 锵不打扰保存在一个地方 我们可以看到它，并汇编代码 被组装成hello.o，这 确实是，默认名称 每当你编译源代码给 编码成目标代码，但不 完全准备好执行它， 因为又迈进了一步 必须发生，并且具有 已经发生的事情在过去几年 周，也许不知情的你。 特别的地方 在CS50 IDE，而这一点， 也将是一个比特的 过于简单化了一会儿， 有，或者是很久以前， 一个称为标准io.c中的文件， 有人编译成 标准io.s或相当于 有人再组装 成标准io.o， 还是原来成 稍有不同的文件 可以有一个不同的格式 共文件扩展名， 但在理论和概念上，正好 这些步骤必须发生某种形式。 这就是说，现在 当我写一个程序， hello.c中，这只是说，你好世界， 而我使用别人的代码 如printf，这是仙界 时间，在一个名为标准io.c中的文件， 后来不知怎的我得把我的 目标代码，我的0和1 而那个人的对象 代码，或0和1 并以某种方式连接成 最后一个文件，名为hello，即 拥有所有的零和 从我的主要功能的， 和所有的零 和那些像printf。 事实上，这最后一道工序是 所谓，链接您的目标代码。 它的输出 是一个可执行文件。 因此，在公平，在 的天，没有结束 由于一个周也改变了，当我们 刚开始编译程序。 事实上，所有的这一直 发生在引擎盖下， 但现在，我们正处在一个位置 在这里，我们实际上可以 梳理出这些不同的步骤。 事实上，在结束 这一天，我们仍然 留下零和一，这 实际上是一个很大的SEGUE现在 到C的另一能力，即 我们已经没有利用最有可能 迄今为止，被称为位运算符。 换句话说，迄今为止，任何时候我们已经 处理C或变量数据，C， 我们已经有像 字符，可漂浮，插件 和长和双打之类的，但 所有这些都是至少八位。 我们从来没有能够 操纵单个位， 即使一个人位，我们 知道，可以代表一个0和1。 现在事实证明，在C，你 可以访问各个位， 如果你知道的语法， 与得到他们。 因此，让我们一起来看看 在位运算符。 所以图为几个符号 我们，那种类型的，以前见过。 我看到一个符号，一个垂直 酒吧和其他一些为好， 并且记得，符号与符号 是我们所见过的。 逻辑运算符，那就是你有 他们两个人在一起，或者逻辑或 运营商，在那里你 有两个竖条。 位运算符，我们将 见位独立运行， 只需使用一个符号，一个 单竖条，插入符号符号 随之而来的，小 波浪线，然后离开 支架左支架，或 右括号右括号。 每个这些具有不同的含义。 事实上，让我们一起来看看。 让我们去老同学今天和使用 从昔日的触摸屏， 已知，为白色板。 而这个白板 将会让我们 发表一些相当简单的符号， 或者更确切地说，一些相当简单的公式， 我们可以再最终 杠杆率，为了 访问个人 在C程序位。 换句话说，让我们做到这一点。 让我们先谈了 矩符号， 这是按位与运算。 换言之，这是 运营商允许 我有一个左手变 典型地，和一个右侧变量， 或者一个人的价值，如果我们和 他们在一起，给了我一个最终的结果。 所以，这是什么意思？ 如果在一个程序中，你有一个变量 这些值的商店之一， 还是让我们保持简单，只 写出零和一独立， 这里是如何的符号操作符。 0符号0将等于0。 现在，这是为什么？ 这是非常相似 布尔表达式， 我们已经迄今为止的讨论。 如果你以后都认为，在0 假的，0是假的，假的，假的 是，正如我们已经讨论 从逻辑上讲，也是假的。 所以，我们得到0在这里。 如果拿0符号 1，清楚，也一样， 将是0，因为对于这 左手边表达式为true或1， 这将需要真正的和真实的。 但在这里，我们有假 而真实，或0和1。 现在再次，如果我们有1符号 0，即，也将是0， 如果我们有1符号1， 最后我们有一个1位。 因此，换句话说，我们没有做 什么有趣的与该运营商 只是还没有，这个符号运算符。 这是按位与运算。 但这些成分 通过它，我们可以做的 有趣的事情，因为我们很快就会看到。 现在，让我们来看看刚才单 竖条在这里就对了。 如果我有一个0位和我 或用，按位 OR运算符，另一0位， 这是怎么回事，给我0。 如果我把一个0位和或用 1位，那么我会得到1。 而事实上，只是 清晰，让我回去， 所以，我的竖线 不能误认为是1的。 让我重写所有的 我1是多一点 显然，让我们接下来看，如果我 有个1或0，这将是一个1， 如果我有1或1中， 也将是一个1。 所以，你可以在逻辑上看到或 经营者的行为非常不同。 这给了我0或0给了我0，但是 所有其他的组合给了我1。 只要我有一个1的 式，其结果将是1。 通过与和对比度 运营商的符号， 只有当我有两个1的中 方程，我居然得到1了。 现在有一些其他的 运营商也是如此。 其中之一是一个涉及多一点。 因此，让我继续前进，抹去 此释放一些空间。 而让我们一起来看看 插入符号符号，只是一瞬间。 这通常是一个 字符，你可以键入 在键盘按住Shift 再一个你顶上美国的数字 键盘。 因此，这是独家 OR运算，异或。 所以，我们刚才看到的或经营人。 这是异或运算符。 什么是真正的区别是什么？ 那么就让我们来看看公式， 并以此作为最终的成分。 0 XOR 0。 我要说的是始终为0。 这是异或的定义。 0 XOR 1将是1。 1异或0将是1， 1 XOR 1将是？ 错了吗？ 还是向右？ 我不知道。 0。 现在到底是怎么回事吗？ 那么想想 该运营商的名称。 异或，以便在 名种，顾名思义， 的回答为仅将是 1，如果输入是排他性的， 完全不同。 因此，这里的输入是 相同的，所以输出为0。 这里的输入是 相同的，所以输出为0。 下面是输出不同，它们 是互斥的，所以输出1。 所以这是非常相似的 而且，它是非常相似的， 或者更确切地说，它是非常相似 或者，但只在专用方式。 这一个不再是1， 因为我们有两个1的， 而不是排他地，它们中的一个。 好吧。 怎么样的人？ 好了波浪线，同时， 其实不错，简单，谢天谢地。 这是一个一元 操作者，这意味着 它仅施加到一个输入端， 一个操作数，可以这么说。 不为左和右。 换句话说，如果你采取的波浪线 0，答案会是相反的。 如果你把波浪的1， 答案会有相反。 所以波浪线操作员 某种程度上否定了一下， 或者翻转位来自 0至1或1至0。 这使我们最终 只有最后两运营商， 所谓左移位，而 所谓向右移位运算符。 让我们来看看如何将这些工作。 左移位运算符，写 有两个尖括号这样， 操作如下。 如果我的输入，还是我操作，向左 移位运算符是很简单1。 我再告诉电脑 左移说明1，说七宿， 其结果是，好像我 采取1，并移动 七宿转移到 左，默认情况下， 我们将假设 的空间权 打算用零填充。 换句话说，1左移7是要 给我一个1，其次是1，2，3， 4，5，6，7个零。 因此，在某种程度上，它可以让你 取少量像1， 并明确使它更 多，在这种方式大得多， 但我们真的要见 更聪明的办法吧 相反，还有， 好吧。 这就是它了三个星期 我们会看到你下一次。 这是CS50。 [音乐播放] 扬声器1：他是在小吃 酒吧吃热软糖圣代。 他拥有了一切在他的脸上。 他穿着巧克力像胡子 扬声器2：你在做什么？ 扬声器3：嗯？ 什么？ 扬声器2：您刚才二次探底？ 你双跌的芯片。 扬声器3：对不起。 扬声器2：你蘸了芯片， 咬了一口，并再次下跌。 扬声器3： 扬声器2：所以，这就像把 你的整个嘴就在畅游。 下一次你把一个芯片， 只是沾了一次，并结束它。 扬声器3：你知道吗，丹？ 你沾要沾的方式。 我会沾，我要沾的方式。