Problem 5.

Implement the following function in a recursive fashion:
bool isSolvable(int x, int y, int c);

This function should return true if there exists nonnegative integers a and b
such that the equation ax + by = c holds true. It should return false otherwise.
(Hard, although not much code)

Ex: isSolvable(7, 5, 45) == true //a == 5 and b == 2
Ex: isSolvable(1, 3, 40) == true //a == 40 and b == 0
Ex: isSolvable(9, 23, 112) == false

bool isSolvable(int x, int y, int c)
{
    if (c<x || c<y) return false;
    
    if (c%x == 0) return true;
    else if (c%y == 0) return true;
    else {
        isSolvable(x, y, c-y);
    }
    return false;
}

int main()
{
    assert(isSolvable(7, 5, 45));
    assert(!isSolvable(9, 23, 112));
    cout << "Passed!" << "\n";
}

Problem 6.

bool isClimbable(int stairs[], int length);
This function takes as input an array of int that represents the stairs (the robot
starts at position 0), as well as the length of the array. It should return true if a
path exists for the robot to reach the end of the stairs, and false otherwise.

Ex: isClimbable({2, 0, 3, 0, 0}, 5) == true
//stairs[0]->stairs[2]->End
Ex: isClimbable({1, 2, 4, 1, 0, 0}, 6) == true
//stairs[0]->stairs[1]->stairs[3]->stairs[2]->End
Ex: isClimbable({4, 0, 0, 1, 2, 1, 1, 0}, 8) == false

답지:

bool isClimbableHelper(int stairs[], bool visited[], int
length, int pos) {
  if (pos < 0) return false;
  if (pos >= length) return true;
  if (stairs[pos] == 0 || visited[pos]) return false;
  visited[pos] = true;
  return isClimbableHelper(stairs, visited, length, pos - stairs[pos]) 
  || isClimbableHelper(stairs, visited, length, pos + stairs[pos]);
}

bool isClimbable(int stairs[], int length) {
  if (length < 0)
  	return false;
  bool* visited = new bool[length];
  for (int x = 0; x < length; x++)
  	visited[x] = false;
  bool res = isClimbableHelper(stairs, visited, length, 0);
  delete[] visited;
  return res;
}

bool isClimbable(int stairs[], int length) 말고 bool isClimbable2(int stairs[], int length, int size) 만듦.

bool isClimbable2(int stairs[], int length, int size) {
    cout << "stairs[0]: " << stairs[0] << "\n";
    if (size == 0) {
        if (length == 0) return true;
        else return false;
    } else {
        return isClimbable2(stairs+1, length-stairs[0], size-1) || isClimbable2(stairs+1, length+stairs[0], size-1);
    }
}

Problem 7.

Implement the function sumOfDigits recursively. The function should return
the sum of all of the digits in a positive integer. (Medium)

int sumOfDigits(int num)
{
    if (num<10) return num;
    else return num%10 + sumOfDigits(num/10);
}

int main()
{
    assert(sumOfDigits(176)); // should return 14
    assert(sumOfDigits(111111)); // should return 6
}

Problem 9.

이거 뭔가가 안되는데 왜 안되는지 모르겠음.
집에가서 확인해볼것.

#include <iostream>
#include "LinkedList.hpp"
using namespace std;

int main()
{
    Node *A = new Node;
    Node* curr = A;
    for (int i=0; i<5; i++){
        curr->data = i;
        curr->next = new Node;
        curr = curr->next;
    }
    delete curr;
    //insertInOrder(A, 8);
    
    cout << "print A" << "\n";
    while (A) {
        cout << A->data << " ";
        A = A->next;
    }
    
    cout << endl;
    
    return 0;
}

Problem 11.

Write a recursive function to reverse a doubly linked list. Assume the linked list
has all its functions implemented. The integer value in each node must not
be changed (but of course the pointers can be).

Node* reverse(Node* head) {
  if (head == nullptr)
     return head;
  
  // swap
  Node* temp = head->next;
  head->next = head->prev;
  head->prev = temp;
  
  if (head->prev == nullptr)
  	return head;
  return reverse(head->prev);
}