Discrete Structures (aka Discrete Math) Problem regarding loop invariants and ma
ID: 3576644 • Letter: D
Question
Discrete Structures (aka Discrete Math) Problem regarding loop invariants and maybe verification:
Please show step by step work for the problem. Please make sure your answer is correct, easy to read, and has answered all parts of the question, please do not answer if you won’t show all work. This is for a discrete structures (math) class. Thanks so much in advance!
Update: "Missing Figure" isn't very clear to what you info you need to answer this.
II The following program is intended to add up the values 1 to N, into variable s (the total) (It illustrates loop unrolling general technique for speeding up code by reducing the number of times the loop test condition is evaluated.) We suggest you use the abbreviation sum (i, j) 0 if jki, and it j if ik j s 0 is CH Bod 2); you will have to think of what m holds while (k-1 m) s k (k+1) k k 2 if (N m) //do nothing The pre-condition of the program is that N> 2 (is needed for termination at least); the post-condition of the program is s sum (1,N) i) Trace the program for a small value of N, and try to understand why it works. ii) State a loop invariant that you could use to prove the program achieves the postcondition if it terminates. iii) Show the formal proof of correctness by adding blank lines between code, and filling it in like in the lecture notes or above In this case, because there is some after the loop end, you will need to push back POST thru {POST) J. This is probably the hardest part to do rightExplanation / Answer
#include <stdio.h>
int main() {
int k=1,s=0,m,n=5;
m=n-(n%2);
if(n>2)
while(k-1!=m)
{
s=s+k+(k+1);
k=k+2;
}
if(n!=m){
s=s+n;
printf("%d",s);
}
return 0;
}
//postcondition:-
#include<stdio.h>
int k=0,i=0,j=0,res=0,ans;
void sum(i,j){
if(j>i){
k=i+1;
res=i+k;
sum(res,res+1);
printf("%d",res);
}
else{
printf("addition not possible");
}
}
1)pass(1,4)
results is:1+2+3+4 = 10
sum(1,4)
condition verifies 4>1
then 1+2=3is made
sum(3,3) is passed then
3+3 is added then becomes 6
sum(6,4) becomes 10
Loop Invariant:
if(i>j){
//write code in opposie way
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.