Become proficient with recursion by implementing the two algorithms below, and m
ID: 3869111 • Letter: B
Question
Become proficient with recursion by implementing the two algorithms below, and manipulating linked lists with recursion. The Fibonacci sequence is the series of integers 0, 1, 1, 2,3,5, 8, 13, 21, 34, 55,.. Note that each element in the series is the sum of the preceding two items. The formula for calculating the nth number of the sequence is given by: fib = {n, if n = 0 or 1 fib(n - 1) + fib(n - 2) n > 1 The following expression defines a function that calculates an approximation of the squareroot of a number, starting with an approximate answer (est), within the specified tolerance (tol). Sqrt (n, est, tol) = {est, if |est^2 - n| lessthanorequalto tol squareroot (n, est^2 + n/2est, tol) if |est^2 - n| > tol Perform the following operations on a linked list of words (strings). The words are to be stored using dynamically allocated memory (not an array). Write functions to perform the following tasks. Insertion Length Shortest and Longest word Contains a word (search) A complete program to calculate Fibonacci numbers, calculate squareroot s and manipulate linked lists of words. A program design sheet. Describe all functions necessary to implement your program. A sample calculation sheet. Show the expected values for both the Fibonacci series and the squareroot .Explanation / Answer
insertion
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
length
// Iterative C program to find length or count of nodes in a linked list
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
shortest and longest
#include <iostream.h>
using namespace std;
#include <ctype.h>
#include <cstdlib>
#include <conio.h>
#include <iomanip.h>
#include <string.h>
void input (char*);
void play(char*, char[5000], int&, int&);
void wordCount (char*);
void longWord (char*, int);
void upper (char*);
void numbers (char*);
void punc (char*);
void main()
{
char string [5000] = {'/0'};
char word[5000] = {'/0'};
int x = 0; int n = 0;
input(string);
play(string, word, x, n);
wordCount(string);
longWord(string, x);
upper(string);
numbers (string);
punc (string);
}
void input (char *enter)
{
int len;
cout<<"Enter sentence(s) ";
cin.getline(enter, 5000);
// cout<<"The string is: " <<enter<<endl;
// len = strlen(enter);
// cout<<"The sentence length is: " <<len<<endl;
// return 0;
}
void play(char *temp, char word[5000], int&x, int &n)
{
int d; int i; int l; int p; int s; int y = 0;
l = strlen(word);
for (i = 0; i < l; i++)
{
d = isdigit(word); p = ispunct(word); s = isspace(word);
if (word == '.' && ispunct(word[i-1]) == 0 && y > 0) n++;
else if (word == '!' && ispunct(word[i-1]) == 0 && y > 0) n++;
else if (word == '?' && ispunct(word[i-1]) == 0 && y > 0) n++;
if (p == 0 && s == 0 && d == 0)
{
*temp *y == word;
y++;
}
else if (ispunct(word[i+1]) == 0 && isspace(word[i+1]) == 0)
{ if (i+1 < l && i > 0 && y > 0) { x++; y = 0; } }
}
}
void wordCount (char *word2)
{
int cnt = 0;
while(*word2 != '')
{
while(isspace(*word2))
{
++word2;
}
if(*word2 != '')
{
++cnt;
while(!isspace(*word2) && *word2 != '')
++word2;
}
}
cout<<"Number of words: "<<cnt<<endl;
}
void upper (char *word2)
{
int caps = 0;
int lower = 0;
int case1 = strlen(word2);
for(int i = 0; i < case1; i++)
{
if(isupper(word2))
caps++;
else if (islower(word2))
lower++;
}
cout<<" Upper Case: "<<caps<<endl;
cout<<"Lower Case: "<<lower<<endl;
}
void numbers (char *word2)
{
int num = 0;
int amount = strlen(word2);
for(int i = 0; i < amount; i++)
{
if(isdigit(word2))
num++;
}
cout<<"Digits: "<<num<<endl;
}
void punc (char *sentence)
{
int marks = 0;
int pncs = strlen(sentence);
for(int i = 0; i < pncs; i++)
{
if(ispunct(sentence))
marks++;
}
cout<<"Punctuation: "<<marks<<endl;
system("pause");
}
//HERE IS MY PROBLEM
void longWord (char *temp, int x )
{
//int x;
int i; int l = 0; int m = 0; int n = 0;
for (i = 0; i < x+1; i++)
{
l = int(strlen(temp));
if (l != '/0' > m)
{
m = l;
n = 0;
}
else if (l == m)
n++;
}
cout << endl << "Longest Word(s): ";
for (i = 0; i < x+1; i++)
{
if (int(strlen(temp) == m))
cout << temp;
if (n > 0 && int( strlen(temp)) == m)
{
//cout << " / ";
n--; }
}
cout << endl;
}
contains a word
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct ListNode {
char* word;
struct ListNode *next;
} ListNode;
typedef struct List {
ListNode *head;
ListNode *tail;
} List;
List* build_list(char* fileName)
{
FILE* file = fopen(fileName, "r");
assert(file != NULL);
List* list = malloc(sizeof(List));
assert(list != NULL);
list->head = NULL;
list->tail = NULL;
char c;
int word_size = 1;
char* word = malloc(word_size);
int word_count = 0;
while ((c = fgetc(file)) != EOF)
{
assert(!ferror(file));
while (c != ' ' && c != EOF)
{
if (word_count == word_size)
{
word_size += 1;
word = realloc(word, word_size);
assert(word != NULL);
}
word[word_count++] = c;
c = fgetc(file);
assert(!ferror(file));
}
word = realloc(word, word_size + 1);
word[word_size] = '';
ListNode *node = malloc(sizeof(ListNode));
assert(node != NULL);
node->next = NULL;
node->word = word;
if (list->head == NULL)
{
list->head = node;
list->tail = node;
}
else
{
list->tail->next = node;
list->tail = node;
}
if (c == EOF)
break;
word_count = 0;
word_size = 1;
word = malloc(word_size);
}
free(word);
assert(!ferror(file));
return list;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.