1. Consider the following algorithm: Algorithm Sum( m , n ) //Input: A positive
ID: 3668621 • Letter: 1
Question
1. Consider the following algorithm:
Algorithm Sum(m, n)
//Input: A positive integer n and another positive integer m n
//Output: ?
sum = 0
for i=m to n do
for j=1 to i do
sum = sum + 5
end for j
end for i
return sum
What does the algorithm compute? Show and determine the formula for the total number of additions (sum = sum + 5) performed by the algorithm.
2. Consider the following recursive algorithm:
Algorithm Recursive(A[0..n-1])
//Input: A list A[0..n-1] of real numbers
//Output: ?
if n == 1 return A[0]
else do
value = Recursive(A[0..n-2])
if value > A[n-1] return value else return A[n-1]
end if
What does the algorithm compute? Establish and solve the recurrence relation for the total number of element comparisons (value > A[n-1]) performed by the algorithm.
Explanation / Answer
1.The algorithm compute that the sum of values incremented by 5.
#include<iostream>
using namespace std;
int sum(int,int);
int main()
{
int m1,n1;
cout<<"Enter the values of m1";
cin>>m1;
cout<<"Enter the values of n1";
cin>>n1;
cout<<"The sum="<<sum(m1,n1);
system("pause");
}
int sum(int m,int n)
{
int sum=0;
for(int i=m;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
sum=sum+5;
}
}
return sum;
}
Sample output:
Enter the values of m1:4
Enter the values of n1:5
The sum=45Press any key to continue . . .
The number of additions =0+5 +10+15+20+25+30+35+40+45=9 =m+n additions
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.