草庐IT

c++ - 循环不变量(特别是 "Accelerated C++"的第 3 章)

coder 2024-02-01 原文

我目前正在学习“Accelerated C++”,只是在第 3 章中遇到了这个问题:

// invariant:
//  we have read count grades so far, and
//  sum is the sum of the first count grades
while (cin >> x) {
    ++count;
   sum  +=  x;
}

作者随后解释说,需要特别注意不变量,因为当输入被读入 x 时,我们将读取 count + 1 等级和因此不变量将是不真实的。同样,当我们递增计数器时,sum 将不再是最后计数成绩的总和(如果您没有猜到,它是计算学生分数的传统程序)。

我不明白为什么这很重要。对于几乎任何其他循环,类似的陈述肯定是正确的吗?例如,这是本书的第一个 while 循环(输出稍后填写):

// invariant: we have written r rows so far
while (r != rows) {
    // write a row of output 
    std::cout << std::endl;
    ++r;
}

一旦我们编写了适当的输出行,在我们递增 r 之前,不变量肯定是假的,就像在另一个例子中一样?

是什么让这两个条件不同?

编辑:感谢您的所有回复。 我想我已经明白了,但在我选择一个“已接受的答案”之前,我会把它放久一点,只是为了确定。到目前为止,所有的回复基本上都同意,所以很难看起来很公平,但我想值得一试。

原始段落,如下要求:

“理解这个循环的不变量需要特别小心,因为 while 中的条件有副作用。那些副作用会影响不变量的真实性:成功执行 cin >> x 使不变量的第一部分 - the 部分这表明我们已经读取了 count grades-false。因此,我们必须更改我们的分析以说明条件本身可能对不变量产生的影响。

我们知道在评估条件之前不变量为真,所以我们知道我们已经读取了计数等级。如果 cin >> x 成功,那么我们现在已经读取了 count + 1 个成绩。我们可以通过递增计数使这部分不变量再次为真。然而,这样做会伪造不变量的第二部分——表示 sum 是第一个 count 成绩总和的部分——因为在我们增加 count 之后,sum 现在是第一个 count 的总和 - 1 个成绩,而不是第一个算成绩。幸运的是,我们可以通过执行 sum += x; 使不变量的第二部分为真。这样整个不变量在这段时间内的后续行程中都为真。

如果条件为假,则意味着我们的输入尝试失败,因此我们没有获得更多数据,因此不变量仍然为真。因此,我们不必考虑 while 结束后条件的副作用。”

最佳答案

一般来说,不变量被理解为仅适用于循环的迭代之间。 (至少我是这样读的!)

一般情况是这样的:

[invariant true];
while (keep going) {
    [state transformation];
    [invariant true];
}

但是在状态转换过程中,你的不变量不一定成立。

作为一个单独的风格注释:如果你想成为一名 super 编码员,与其将不变量留在注释中,不如将它们变成断言!

// Loop invariant: x+y = -4
for (int x = 0; x < 10; x++) {
    [do something];
    assert(x+y == -4);  // Loop invariant here!
}

这样你就有了自检代码。

关于c++ - 循环不变量(特别是 "Accelerated C++"的第 3 章),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2936044/

有关c++ - 循环不变量(特别是 "Accelerated C++"的第 3 章)的更多相关文章

  1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身,new.html.erb,有代码:当我运行rspec时,它失败了:1)messages/new.html.erbshou

  2. ruby-on-rails - 由于 "wkhtmltopdf",PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中,我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  3. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法,所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少,我以前从未做过这种事情。我的解析器表现得好像有一个无限循环,但没有堆栈跟踪;事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗?我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上,以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  4. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组,我需要根据最早的事件循环打印。在这种情况下,我需要打印付款和维护日期,如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询,用于查找maintenance和payment项目(非排他性查询),并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  5. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本,我按照提供的说明安装了arubagem。它在我的Gemfile中,我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作,我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了,但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  6. ruby-on-rails - 如何优雅地重启 thin + nginx? - 2

    我的瘦服务器配置了nginx,我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例,但找不到好的解决方案。有没有人能做到这一点? 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器,例如server{listen80;server

  7. ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量? - 2

    我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用? 最佳答案 我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击

  8. ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2

    在我的应用程序中,我需要能够找到所有数字子字符串,然后扫描每个子字符串,找到第一个匹配范围(例如5到15之间)的子字符串,并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串,例如,re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项,并且只替换第N个匹配项,我该怎么做?例如,如果我想替换第三个匹配项“10”(匹配项[2]),我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg

  9. ruby - 通过 ruby​​ 进程共享变量 - 2

    我正在编写一个gem,我必须在其中fork两个启动两个webrick服务器的进程。我想通过基类的类方法启动这个服务器,因为应该只有这两个服务器在运行,而不是多个。在运行时,我想调用这两个服务器上的一些方法来更改变量。我的问题是,我无法通过基类的类方法访问fork的实例变量。此外,我不能在我的基类中使用线程,因为在幕后我正在使用另一个不是线程安全的库。所以我必须将每个服务器派生到它自己的进程。我用类变量试过了,比如@@server。但是当我试图通过基类访问这个变量时,它是nil。我读到在Ruby中不可能在分支之间共享类变量,对吗?那么,还有其他解决办法吗?我考虑过使用单例,但我不确定这是

  10. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容? - 2

    我是一个Rails初学者,但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现),但没有得到任何结果。有什么建议吗?我知道Rails调试器,但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

随机推荐