- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
你好,我想证明一维数组中包含的所有值的平均值的计算,
到目前为止我有以下程序:
#include <stdbool.h>
typedef unsigned int size_t;
typedef struct Average avg;
struct Average
{
bool success;
float average;
};
/*@
axiomatic Float_Div{
logic real f_div(real a,real b) = a/b ;
axiom div:
\forall real q,a,b; 0 != b ==>
(a == b*q <==> q == f_div(a, b));
axiom split :
\forall real q,a,b,c; 0 != b ==>
f_div(a + c , b) == f_div(a,b) + f_div(c,b);
}
axiomatic Average {
logic real average(int * t, integer start, integer stop, integer size);
axiom average_0:
\forall int *t, integer start , integer stop, size;
start >= stop ==> average(t,start, stop, size) == 0;
axiom average_n:
\forall int *t, integer start , integer stop, integer size;
start < stop && size >0 ==>
average(t,start, stop, size) ==
f_div((real)stop-1 ,(real) size) +( average(t,start, stop-1, size) );
axiom average_split :
\forall int *t, integer start ,integer middle, integer stop, integer size;
start < middle < stop && size >0 ==>
average(t,start, stop, size) == average(t,start, middle, size) + average(t,middle, stop, size);
axiom average_unit :
\forall int *t, integer start , integer stop, integer size;
start == stop-1 && size >0 ==>
average(t,start, stop, size) == f_div((real)stop-1 ,(real) size);
}
*/
/*@
requires \valid(array + (0..size-1));
ensures (!\result.success) ==> size == 0 ;
ensures (\result.success) ==> \result.average == average(array, 0, size, size);
assigns \nothing;
*/
avg average(int * array, size_t size){
avg ret;
ret.success = true ;
ret.average = 0 ;
if (size == 0){
ret.success = false;
return ret;
}
float average = 0;
/*@
loop assigns i, average;
loop invariant 0 <= i <= size;
loop invariant average(array , 0, i , size) == average;
*/
for (size_t i = 0 ; i < size ; i ++){
float value = ((float)array[i] / size);
average += value;
}
ret.average = average ;
return ret;
}
frama-c 未能成功证明此循环不变式:
loop invariant average(array , 0, i , size) == average;
我做错了什么吗?我不知道我的问题是否来自 float 的精度。我尝试了很多断言,但它也不起作用它可以在 Frama-c 中完成吗?
编辑:
我终于证明了我的功能,我在加和之前先做除法,因为每次我尝试先求和都会溢出。
问题是我需要证明我的总和没有溢出。所以我导入了 limits.h并添加一个新的循环不变量:INT_MIN * i <= sum <= INT_MAX * i;
所以我的代码现在看起来像这样:
#include <stdbool.h>
#include <limits.h>
typedef unsigned int size_t;
typedef struct Average avg;
struct Average
{
bool success;
long long average;
};
/*@
axiomatic Sum{
logic integer sum(int * t , integer start, integer end);
axiom sum_false :
\forall int *t, integer start , integer stop;
start >= stop ==> sum(t,start,stop) == 0;
axiom sum_true_start :
\forall int *t, integer start , integer stop;
0 <= start < stop ==>
sum(t,start,stop) == sum(t,start,start+1) + sum(t,start+1,stop);
axiom sum_true_end :
\forall int *t, integer start , integer stop;
0 <= start < stop ==>
sum(t,start,stop) == sum(t,start,stop-1) + sum(t,stop-1,stop);
axiom sum_split :
\forall int *t, integer start , integer stop, integer middle;
0 <= start<= middle < stop ==>
sum(t,start,stop) == sum(t,start,middle) + sum(t,middle,stop);
axiom sum_alone :
\forall int *t, integer start;
(0<=start)
==>
sum(t,start,start+1) == t[start] ;
}
*/
/*@
requires \valid(array + (0..size-1));
ensures (!\result.success) ==> size == 0 ;
ensures (\result.success) ==> (\result.average == sum(array,0,size)/size) ;
assigns \nothing;
*/
avg average(int * array, size_t size){
//we use a structure to be sure that the function finish without error
avg ret;
ret.success = true ;
ret.average = 0 ;
if (size == 0){
//if the size == 0 the function will fail
ret.success = false;
return ret;
}
else{
/*
the average is the sum of all the element of the array divided by the size
An int is between - 2^15-1 and 2^15-1 that imply that the sum of
all the element of an array is between
-2^15 * size and 2^15 * size as size is between 0 and 2^16
the sum is between -2^31 and 2^31
a long long is between -2^63 and 2^63
the sum of all the element can be inside a long long.
*/
long long sum = 0;
/*@
loop assigns i, sum ;
loop invariant 0 <= i <= size;
loop invariant sum == sum(array,0,i);
loop invariant INT_MIN * i <= sum <= INT_MAX * i;
*/
for (size_t i = 0 ; i < size ; i ++){
//@assert INT_MIN * i <= sum <= INT_MAX * i;
sum += array[i];
//@assert i+1 <= size;
//@assert INT_MIN * (i+1) <= sum <= INT_MAX * (i+1);
//@assert ((LLONG_MIN < INT_MIN * size ) && (LLONG_MAX > INT_MAX* size));
//@assert LLONG_MIN <= sum <= LLONG_MAX;
//@assert sum == sum(array,0,i) + array[i];
}
ret.average = sum/size ;
return ret;
}
}
我让断言,但我确信其中很多都是无用的。
最佳答案
I want to prove the computation of the average of all the values contained in a 1d array
对于精确的数学,避免 float 。
因为 array[]
是 int
,坚持使用整数数学。
建议重写代码。
用于测试“一维数组中包含的所有值的平均值”的伪代码
// Compute sum of all elements of the array
wide_integer_type sum = 0
for (i=0; i<n; i++)
sum += array[i]
for (i=0; i<n; i++)
// below incurs no rounding like `array[i] == (double)sum/n` might
if ((cast to wide_integer_type)array[i] * n == sum)
print "average found!" sum/n
关于c - 证明数组的平均值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59358989/
我正在尝试创建一个包含 int[][] 项的数组 即 int version0Indexes[][4] = { {1,2,3,4}, {5,6,7,8} }; int version1Indexes[
我有一个整数数组: private int array[]; 如果我还有一个名为 add 的方法,那么以下有什么区别: public void add(int value) { array[va
当您尝试在 JavaScript 中将一个数组添加到另一个数组时,它会将其转换为一个字符串。通常,当以另一种语言执行此操作时,列表会合并。 JavaScript [1, 2] + [3, 4] = "
根据我正在阅读的教程,如果您想创建一个包含 5 列和 3 行的表格来表示这样的数据... 45 4 34 99 56 3 23 99 43 2 1 1 0 43 67 ...它说你可以使用下
我通常使用 python 编写脚本/程序,但最近开始使用 JavaScript 进行编程,并且在使用数组时遇到了一些问题。 在 python 中,当我创建一个数组并使用 for x in y 时,我得
我有一个这样的数组: temp = [ 'data1', ['data1_a','data1_b'], ['data2_a','data2_b','data2_c'] ]; // 我想使用 toStr
rent_property (table name) id fullName propertyName 1 A House Name1 2 B
这个问题在这里已经有了答案: 关闭13年前。 Possible Duplicate: In C arrays why is this true? a[5] == 5[a] array[index] 和
使用 Excel 2013。经过多年的寻找和适应,我的第一篇文章。 我正在尝试将当前 App 用户(即“John Smith”)与他的电子邮件地址“jsmith@work.com”进行匹配。 使用两个
当仅在一个边距上操作时,apply 似乎不会重新组装 3D 数组。考虑: arr 1),但对我来说仍然很奇怪,如果一个函数返回一个具有尺寸的对象,那么它们基本上会被忽略。 最佳答案 这是一个不太理
我有一个包含 GPS 坐标的 MySQL 数据库。这是我检索坐标的部分 PHP 代码; $sql = "SELECT lat, lon FROM gps_data"; $stmt=$db->query
我需要找到一种方法来执行这个操作,我有一个形状数组 [批量大小, 150, 1] 代表 batch_size 整数序列,每个序列有 150 个元素长,但在每个序列中都有很多添加的零,以使所有序列具有相
我必须通过 url 中的 json 获取文本。 层次结构如下: 对象>数组>对象>数组>对象。 我想用这段代码获取文本。但是我收到错误 :org.json.JSONException: No valu
enter code here- (void)viewDidLoad { NSMutableArray *imageViewArray= [[NSMutableArray alloc] init];
知道如何对二维字符串数组执行修剪操作,例如使用 Java 流 API 进行 3x3 并将其收集回相同维度的 3x3 数组? 重点是避免使用显式的 for 循环。 当前的解决方案只是简单地执行一个 fo
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我有来自 ASP.NET Web 服务的以下 XML 输出: 1710 1711 1712 1713
如果我有一个对象todo作为您状态的一部分,并且该对象包含数组列表,则列表内部有对象,在这些对象内部还有另一个数组listItems。如何更新数组 listItems 中 id 为“poi098”的对
我想将最大长度为 8 的 bool 数组打包成一个字节,通过网络发送它,然后将其解压回 bool 数组。已经在这里尝试了一些解决方案,但没有用。我正在使用单声道。 我制作了 BitArray,然后尝试
我们的数据库中有这个字段指示一周中的每一天的真/假标志,如下所示:'1111110' 我需要将此值转换为 boolean 数组。 为此,我编写了以下代码: char[] freqs = weekday
我是一名优秀的程序员,十分优秀!