[go: up one dir, main page]
Scribd
Upload
1 views4 pages

assig 3 dsa

data structure

Uploaded by

kjkhushijain1401
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
1 views4 pages

assig 3 dsa

data structure

Uploaded by

kjkhushijain1401
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 4

1-Write a RECURSIVE program which computes the sum of the series m2 + (m+1)2

+ . . . . .
. . .+n2
and prints the sum. Test the program by assigning m=2, n=6.
sol-
#include <stdio.h>

int series(int m, int n) {


if (n < m) {
return 0;
}
return (n * n) + series(m, n - 1); // Recursive
}

int main() {
int m = 2, n = 6;
int result;

result = series(m, n);


printf("The sum of squares from %d^2 to %d^2 is: %d\n", m, n, result);

return 0;
}

2-Write a program to read integers from a file arr.txt. The first integer on the
file would be
size of array N. The next N elements would be elements of the array A. Write a
recursive
program which prints the sum of array elements. Create your own file arr.txt and
test your
program.
Sumarray(A, n);

sol-
#include <stdio.h>
int Sumarray(int A[], int n) {
if (n == 0) {
return 0;
}
return A[n-1] + Sumarray(A, n - 1);
}

int main() {
FILE *file;
int N;
int i;

file = fopen("arr.txt", "r");


if (file == NULL) {
printf("Error: Could not open the file.\n");
return 1;
}

fscanf(file, "%d", &N);


int A[N];
for (i = 0; i < N; i++) {
fscanf(file, "%d", &A[i]);
}
fclose(file);

int sum = Sumarray(A, N);

printf("The sum of the array elements is: %d\n", sum);

return 0;
}
3-Write a recursive program which checks if a sorted array contains a specified
value. The
program should count and print number of elements searched by it. It should also
print the
location of the value in the array. If the value is not found, it should print –1.
Create an
array [ 8 12 15 26 30 37 42 50 56 62 76 82 84 88 92 98]. Test your program for
values 12, 98 and 11.
Binary search program, count number of times array elements are searched.
sol-#include <stdio.h>

// Recursive binary search function


int binarySearch(int arr[], int left, int right, int value, int *count) {
(*count)++; // Increment the count of elements searched

if (right >= left) {


int mid = left + (right - left) / 2;

if (arr[mid] == value) {
return mid; // Return the index if found
}
if (arr[mid] > value) {
return binarySearch(arr, left, mid - 1, value, count); // Search in the
left half
}
return binarySearch(arr, mid + 1, right, value, count); // Search in the
right half
}
return -1; // Return -1 if value not found
}

int main() {
int arr[] = {8, 12, 15, 26, 30, 37, 42, 50, 56, 62, 76, 82, 84, 88, 92, 98};
int size = sizeof(arr) / sizeof(arr[0]);
int value, result, count;
int testValues[] = {12, 98, 11};

for (int i = 0; i < 3; i++) {


value = testValues[i];
count = 0;

result = binarySearch(arr, 0, size - 1, value, &count);

if (result != -1) {
printf("Value %d found at index %d. Elements searched: %d\n", value,
result, count);
} else {
printf("Value %d not found. Elements searched: %d. Returned: -1\n",
value, count);
}
}

return 0;
}
4-Here are two functions to compute an
. In the main program assign a as 2 and n as 64 and
call these functions one by one . Figure out the ratio of the time taken by the two
functions.
Attach the functions to a main program. In the program call the functions
separately k
times ( a very large number) and note CPU time?
#include <stdio.h>
#include <time.h>

int fpow1(double a, int n) {


if (n == 0) return 1;
else {
if (n % 2 == 0) return fpow1(a, n / 2) * fpow1(a, n / 2);
else return a * fpow1(a, n / 2) * fpow1(a, n / 2);
}
}

int fpow2(double a, int n) {


if (n == 0) return 1;
else {
int b = fpow2(a, n / 2);
if (n % 2 == 0) return b * b;
else return a * b * b;
}
}

int main() {
double a = 2;
int n = 64;
int k = 10000;

clock_t start, end;


double cpu_time_used;

start = clock();
for (int i = 0; i < k; i++) {
fpow1(a, n);
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Time taken by Function 1: %f seconds\n", cpu_time_used);

start = clock();
for (int i = 0; i < k; i++) {
fpow2(a, n);
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Time taken by Function 2: %f seconds\n", cpu_time_used);

return 0;
}
5-Given a Tower of Hanoi problem, in which 𝑛 disks in Pole A need to move to Pole
C by using
temporary pole B. Moving disk needs to follow following rule:
 You need to move all of the disks from the first tower to the last tower
 Only a smaller disk can sit on top a Larger disk
 The middle tower can be used to temporarily hold disks
A B C
Now write a function int NumOfMoves(int diskCount), which takes total disk count as
input and
produce number of valid moves as output?
sol-#include <stdio.h>

int NumOfMoves(int diskCount) {


if (diskCount == 0) {
return 0;
} else {
return 2 * NumOfMoves(diskCount - 1) + 1;
}
}

int main() {
int diskCount;

printf("Enter the number of disks: ");


scanf("%d", &diskCount);

printf("Number of moves required: %d\n", NumOfMoves(diskCount));

return 0;
}

You might also like