images/Thumbs.db

public class QuickSort {

public static void main(String[] args) {

int[] a = { 4, 3, 7, 11, 2, 6, 5 };

quick_sort(a, 0, 6);

for(int v : a){

System.out.print(v);

System.out.print(" ");

}

}

public static void quick_sort(int[] a, int begin, int end) {

if(begin >= end)

return;

int left = begin, right = end;

int pivot_value = a[left];

while (left < right)

{

if (a[left+1] < pivot_value) {

a[left] = a[left+1];

left++;

} else {

int temp = a[left + 1];

a[left + 1] = a[right];

a[right] = temp;

right--;

}

}

a[left] = pivot_value;

quick_sort(a, begin, left - 1);

quick_sort(a, left + 1, end);

}

}

#include <iostream>

void reverse(int[], int);

void output(int[], int);

int main(){

int array[] = { 5 , 4 , 10 , 1 , 7 , 9 , 2 };

reverse(array, 7);

output(array, 7);

return 0;

}

void reverse(int array[], int length){

int left = 0;

int right = length - 1;

while(left < right){

int temp = array[left];

array[left] = array[right];

array[right] = temp;

left ++;

right --;

}

}

void output(int array[], int length){

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

std::cout << array[i] << std::endl;

}

}

#include <iostream>

using namespace std;

int binary_search(int a[], int key, int begin, int end){

if(begin >= end)

return -1; //array is empty, not found

int middle = (begin + end) / 2;

if(a[middle] > key)

return binary_search(a, key, begin, middle);

else if(a[middle] < key)

return binary_search(a, key, middle + 1, end);

else

return middle;

}

int binary_search_iterative(int a[], int key, int begin, int end){

int middle;

while(begin < end){

middle = (begin + end) / 2;

if(a[middle] > key)

end = middle;

else if(a[middle] < key)

begin = middle + 1;

else

return middle;

}

return -1; //array is empty, not found

}

int main(){

int a[] = { 1, 3, 5, 7, 9};

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

cout << "Searching " << i << endl;

cout << " Position is " << binary_search_iterative(a, i, 0, 5) << endl;

}

return 0;

}

#include <iostream>

int fib(int n){

if(n < 2)

return n;

else

return fib(n - 1) + fib(n - 2);

}

int main(){

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

std::cout << fib(i) << std::endl;

}

}

#include <iostream>

using namespace std;

int gcd_mod(int m, int n){

if(n == 0)

return m;

else

return gcd_mod(n, m % n);

}

int gcd_sub(int m, int n){

if(m == n || n == 0)

return m;

if(m == 0)

return n;

if(m > n)

return gcd_sub(n, m - n);

else

return gcd_sub(m, n - m);

}

int gcd(int m, int n){

if (m == n)

return m;

if (m == 0)

return n;

if (n == 0)

return m;

// look for factors of 2

if (~m & 1) // m is even

{

if (n & 1) // n is odd

return gcd(m >> 1, n);

else // both m and n are even

return gcd(m >> 1, n >> 1) << 1;

}

if (~n & 1) // m is odd, n is even

return gcd(m, n >> 1);

// reduce larger argument

if (m > n)

return gcd((m - n) >> 1, n);

return gcd((n - m) >> 1, m);

}

int main(){

cout << gcd_sub(99, 66) << endl;

cout << gcd_mod(99, 66) << endl;

cout << gcd(99, 66) << endl;

return 0;

}

#include <iostream>

class joseph_circle{

int* next_persons; //array of the indexes of next person

int circle_length;

int tail;

joseph_circle(int circle_length) : circle_length(circle_length){

next_persons = new int[circle_length];

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

next_persons[i] = (i + 1) % circle_length; //points to next person in the circle

}

tail = circle_length - 1;

}

void eliminate(int step) {

int p = tail;

while(next_persons[p] != p){ //equivalent to p->next != p

//while more than one element in the circle

for(int i = 0; i < step - 1; i++){

p = next_persons[p]; //go forward

}

int eliminated_node = next_persons[p]; //eliminate the next one

next_persons[p] = next_persons[next_persons[p]];

if(eliminated_node == tail)

tail = p; //update tail

std::cout << "deleting:" << eliminated_node << std::endl;

output();

}

}

void output(){

int p = tail;

while(true){

p = next_persons[p];

std::cout << p << " ";

if(p == tail)

break; //reach the last element of the circle

}

std::cout << std::endl;

}

};

int main(){

joseph_circle circle(6);

circle.eliminate(3); //eliminate using a step of 3

return 0;

}

#include <iostream>

struct node{

int payload;

node* next;

node(int payload) {this->payload = payload;};

};

class joseph_circle{

node* tail;

node* eliminate_ptr;

joseph_circle() { tail = nullptr; }

//add a new node to joseph circle

void add(int value){

if(tail == nullptr){ //if the joseph circle is empty, modify tail.

tail = new node(value);

tail->next = tail;

}else{ //insert new node as the tail of the circle

node* new_node = new node(value);

new_node->next = tail->next;

tail->next = new_node;

tail = new_node;

}

}

void eliminate(int step) {

node* p = tail;

while(p != nullptr && p->next != p){

//while more than one element in the circle

for(int i = 0; i < step - 1; i++){

p = p->next; //go forward

}

node* eliminated_node = p->next; //eliminate the next one

p->next = p->next->next;

if(eliminated_node == tail)

tail = p; //update tail

std::cout << "deleting:" << eliminated_node->payload << std::endl;

delete eliminated_node;

output();

}

}

void output(){

node* p = tail;

while(p != nullptr){

p = p -> next;

std::cout << p->payload << " ";

if(p == tail)

break; //reach the last element of the circle

}

std::cout << std::endl;

}

};

int main(){

joseph_circle circle;

//insert 6 nodes

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

circle.add(i);

}

circle.eliminate(3); //eliminate using a step of 3

return 0;

}

#include <iostream>

struct node{

int payload;

node* next;

};

node* reverse_recursive(node* head){

if(head==nullptr || head->next==nullptr)

return head;

node* second = head->next;

node* new_head = reverse_recursive(second);

second->next = head;

head->next = nullptr;

return new_head;

}

node* reverse(node* head){

if(head == nullptr || head->next == nullptr)

return head;

node* p = head->next;

node* p_previous = head;

head->next = nullptr;

while(p != nullptr){

node* p_next = p->next;

p->next = p_previous;

p_previous = p;

p = p_next;

}

return p_previous; //new_head

}

int main(){

node* head = nullptr;

//insert 10 nodes

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

node* new_node = new node;

new_node->payload = i * 10;

new_node->next = head;

head = new_node;

}

head = reverse_recursive(head);

//output each node in the linked-list

node* iterator = head;

while(iterator){

std::cout << iterator->payload << std::endl;

iterator = iterator->next;

}

return 0;

}