Consider the following definitions of three function: fun fsum(f,0) = 0 |fsum(f,
ID: 655736 • Letter: C
Question
Consider the following definitions of three function:
fun fsum(f,0) = 0 |fsum(f,n) = f(n)+fsum(f,n-1);
fun tfsum(f,0,c) = c |tfsum(f,n,c) = tfsum(f,n-1,f(n)+c);
fun kfsum(f,0,K) = K 0 |kfsum(f,n,K) = kfsum(f,n-1, fn v=>K(f(n)+v));
(a) State an appropriate equivalence between fsum and tfsum and give an inductive proof of it.
(b) State an appropriate equivalence between fsum and kfsum and give an inductive proof of it. In each case be sure to state the property you are proving and how it demonstrates the equivalence between the two functions. Be careful with the handling of (universally) quantified variables. Be sure to justify each step of your proofs.
Explanation / Answer
(a)
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long *st2 = (long long *)malloc(sizeof(long long)*100000*100000);
int main()
{
int n,q;
int typ,x;
long long mi,ni,sum=0,y;
scanf("%d",&n);
long long arr[n],tsum[n+1],fsum[n],tfsum[n+1];
int fun[n][2];
tsum[0]=0;
tfsum[0]=0;
for(int i=0;i<n;i++)
{
scanf("%lld",&arr[i]);
tsum[i+1]=tsum[i]+arr[i];
}
for(int i=0;i<n;i++)
{
scanf("%d %d",&fun[i][0],&fun[i][1]);
fsum[i]=tsum[fun[i][1]]-tsum[fun[i][0]-1];
tfsum[i+1]=fsum[i]+tfsum[i];
}
scanf("%d",&q);
while(q-->0)
{
scanf("%d %d %lld",&typ,&x,&y);
sum=0;
if(typ==1)
{
arr[x-1]=y;
for(int i=0;i<n;i++)
{
tsum[i+1]=tsum[i]+arr[i];
}
for(int i=0;i<n;i++)
{
fsum[i]=tsum[fun[i][1]]-tsum[fun[i][0]-1];
tfsum[i+1]=fsum[i]+tfsum[i];
}
}
else if(typ==2)
{
mi=x;ni=y;
sum=tfsum[ni]-tfsum[mi-1];
printf("%lld ",sum);
}
}
free(st2);
return 0;
}