Danh scramble word
// Online C compiler to run C program online
#include <stdio.h>
#include <string.h>
void printf_str(char str[]){
int n = strlen(str);
for(int i=0;i<n;++i){
printf("%c ",str[i]);
}
printf("\n");
}
void swap(char two_words[]){
int n = strlen(two_words)-1;
char temp;
temp = two_words[0];
two_words[0] = two_words[1];
two_words[1] = temp;
}
void scramble(char remain_str[]){
char two_words[2];
int n = strlen(remain_str);
char words[n];
int i,j;
strcpy(words,remain_str);
//printf_str(remain_str);
//printf_str(words);
for(i=0;i<n;++i){
for(j=0;j<n;++j){
if(i==j)
continue;
two_words[0] = words[i];
two_words[1] = words[j];
swap(two_words);
words[i] = two_words[0];
words[j] = two_words[1];
if(strcmp(remain_str, words) != 0)
printf_str(words);
}
}
}
int main() {
char words[]="12", temp;
char asd[]="1234";
printf_str(words);
swap(words);
printf_str(words);
//printf_str(asd);
scramble(asd);
return 0;
}
// Online C compiler to run C program online
#include <stdio.h>
#define ARRAY_SIZE 3
void swap(char *a, char *b);
void printout(int arr[], int ARRAY_SIZE);
int main() {
int a[ARRAY_SIZE]={1,2,3};
printf("%d",a[4]);
return 0;
void swap(char *a, char *b){
char temp = *a;
*a = *b;
*b = temp;
return;
void printout(int arr[], int size){
for(int i=0;i<size;++i);
}
Fibonacci sequence step-by-step.
#include <stdio.h>
/* Output the Fibonacci sequence step-by-step.
Fibonacci sequence starts as:
0 1 1 2 3 5 8 13 21 ... in which the first
two numbers are 0 and 1 and each additional
number is the sum of the previous two numbers
*/
void ComputeFibonacci(int fibNum1, int fibNum2, int runCnt) {
printf("%d + %d = %d\n", fibNum1, fibNum2, fibNum1 + fibNum2);
if (runCnt <= 1) { // Base case: Ran for user specified
// number of steps, do nothing
}
else { // Recursive case: compute next value
ComputeFibonacci(fibNum2, fibNum1 + fibNum2, runCnt - 1);
}
}
int main(void) {
int runFor; // User specified number of values computed
// Output program description
printf("This program outputs the\n");
printf("Fibonacci sequence step-by-step,\n");
printf("starting after the first 0 and 1.\n\n");
// Prompt user for number of values to compute
printf("How many steps would you like? ");
scanf("%d", &runFor);
// Output first two Fibonacci values, call recursive function
printf("0\n1\n");
ComputeFibonacci(0, 1, runFor);
return 0;
}
Calculate greatest common divisor of two numbers.
#include <stdio.h>
/* Determine the greatest common divisor
of two numbers, e.g. GCD(8, 12) = 4
*/
int GCDCalculator(int inNum1, int inNum2) {
int gcdVal; // Holds GCD results
if(inNum1 == inNum2) { // Base case: Numbers are equal
gcdVal = inNum1; // return value
}
else { // Recursive case: subtract smaller from larger
if (inNum1 > inNum2) { // call function with new values
gcdVal = GCDCalculator(inNum1 - inNum2, inNum2);
}
else {
gcdVal = GCDCalculator(inNum1, inNum2 - inNum1);
}
}
return gcdVal;
}
int main(void) {
int gcdInput1; // First input to GCD calc
int gcdInput2; // Second input to GCD calc
int gcdOutput; // Result of GCD
// Print program function
printf("This program outputs the greatest \n");
printf("common divisor of two numbers.\n");
// Prompt user for input
printf("Enter first number: ");
scanf("%d", &gcdInput1);
printf("Enter second number: ");
scanf("%d", &gcdInput2);
// Check user values are > 1, call recursive GCD function
if ((gcdInput1 < 1) || (gcdInput2 < 1)) {
printf("Note: Neither value can be below 1.\n");
}
else {
gcdOutput = GCDCalculator(gcdInput1, gcdInput2);
printf("Greatest common divisor = %d\n", gcdOutput);
}
return 0;
}
Scramble a word's letters in every possible way.
#include <stdio.h>
#include <string.h>
const int MAX_ARR_SIZE = 50; // Word size limit
void RemoveFromIndex(char* origString, int remLoc); // Remove letter at location i
from string c
void InsertAtIndex(char* origString, char* addChar,
int addLoc); // Add letter n to location i of
string c
/* Output every possible combination of a word.
Each recursive call moves a letter from
remainLetters" to scramLetters".
*/
void ScrambleLetters(char* remainLetters, // Remaining letters
char* scramLetters) { // Scrambled letters
char tmpString[2]; // Using c string for access to strcat
int i; // Loop index
tmpString[1] = '\0';
if(strlen(remainLetters) == 0) { // Base case: All letters used
printf("%s\n",scramLetters);
}
else { // Recursive case: move a letter from
// remaining to scrambled letters
for (i = 0; i < strlen(remainLetters); ++i) {
// Move letter to scrambled letters
tmpString[0] = remainLetters[i];
strcat(scramLetters, tmpString);
RemoveFromIndex(remainLetters, i);
ScrambleLetters(remainLetters, scramLetters);
// Put letter back in remaining letters
scramLetters[strlen(scramLetters)-1]='\0';
InsertAtIndex(remainLetters, tmpString, i);
}
}
}
int main(void) {
char wordScramble[50]; // User defined word to scramble. 50 is MAX_ARR_SIZE
char finishScramble[50]; // Temp string already scrambled. 50 is MAX_ARR_SIZE
// Init strings
strcpy(wordScramble, "");
strcpy(finishScramble, "");
// Prompt user for input
printf("Enter a word to be scrambled: ");
scanf("%s", wordScramble);
// Call recursive function
ScrambleLetters(wordScramble, finishScramble);
return 0;
}
// Remove letter at location remLoc from string origString
void RemoveFromIndex(char* origString, int remLoc) {
char tmpString[50]; // Temp string to extract char. 50 is MAX_ARR_SIZE
strcpy(tmpString, ""); // Init string
strncat(tmpString, origString, remLoc); // Copy before location remLoc
strncat(tmpString, origString + remLoc + 1,
strlen(origString) - remLoc); // Copy after location remLoc
strcpy(origString, tmpString); // Copy back to orignal string
}
// Add letter addChar to location addLoc of string origString
void InsertAtIndex(char* origString, char* addChar, int addLoc) {
char tmpString[50]; // Temp string to add char. 50 is MAX_ARR_SIZE
strcpy(tmpString,""); // Init string
strncat(tmpString, origString, addLoc); // Copy before location addLoc
strncat(tmpString, addChar, 1); // Copy letter addChar to location addLoc
strncat(tmpString, origString + addLoc,
strlen(origString) - addLoc); // Copy after location addLoc
strcpy(origString, tmpString);
}
Shopping spree in which a user can fit 3 items in a
shopping bag.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
typedef struct Item_struct {
char itemName[50]; // Name of item
int priceDollars; // Price of item
} Item;
const int TOTAL_ITEMS = 4; // Total number of items
available
const unsigned int MAX_SHOPPING_BAG_SIZE = 3; // Max number of items in
shopping bag
/* Output every possible combination of items that
fit in a shopping bag. Each recursive call moves
one item into the bag.
*/
void ShoppingBagCombinations(Item* currBag, // Bag contents
Item* remainingItems, // Available items
bool* beenAdded, // Items already in
shopping bag
int bagCnt) { // Current shopping bag
size
int bagValue; // Cost of items in shopping bag
int i; // Loop index
if (bagCnt == MAX_SHOPPING_BAG_SIZE) { // Base case: Shopping bag full
bagValue = 0;
for (i = 0; i < bagCnt; ++i) {
printf("%s ", currBag[i].itemName);
bagValue += currBag[i].priceDollars;
}
printf("= $%d\n", bagValue);
}
else { // Recursive case: move one
for (i = 0; i < TOTAL_ITEMS; ++i) { // item to bag
if (!beenAdded[i]) {
// Move item to bag
beenAdded[i] = true;
currBag[bagCnt] = remainingItems[i];
ShoppingBagCombinations(currBag, remainingItems,
beenAdded, bagCnt + 1);
// Take item out of bag
beenAdded[i] = false;
}
}
}
}
int main(void) {
Item* possibleItems = NULL; // Possible shopping items
Item* shoppingBag = NULL; // Current shopping bag
bool* itemBeenAdded = NULL; // Track if item already in bag
Item tmpGroceryItem; // Temp item
possibleItems = (Item*)malloc(sizeof(Item) * TOTAL_ITEMS);
shoppingBag = (Item*)malloc(sizeof(Item) * TOTAL_ITEMS);
itemBeenAdded = (bool*)malloc(sizeof(bool) * TOTAL_ITEMS);
// No items added yet
itemBeenAdded[0] = false;
itemBeenAdded[1] = false;
itemBeenAdded[2] = false;
itemBeenAdded[3] = false;
// Populate grocery with different items
strcpy([Link], "Milk");
[Link] = 2;
possibleItems[0] = tmpGroceryItem;
strcpy([Link], "Belt");
[Link] = 24;
possibleItems[1] = tmpGroceryItem;
strcpy([Link], "Toys");
[Link] = 19;
possibleItems[2] = tmpGroceryItem;
strcpy([Link], "Cups");
[Link] = 12;
possibleItems[3] = tmpGroceryItem;
// Try different combinations of three items
ShoppingBagCombinations(shoppingBag, possibleItems,
itemBeenAdded, 0);
return 0;
}
Find distance of traveling to 3 cities.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
const int NUM_CITIES = 3; // Number of cities
int cityDistances[3][3]; // Distance between cities
char cityNames[3][50]; // City names
/* Output every possible travel path.
Each recursive call moves to a new city.
*/
void TravelPaths(int* currPath, int* toVisit,
bool* haveBeen, int cityCnt) {
int totalDist; // Total distance given current path
int i; // Loop index
if (cityCnt == NUM_CITIES) { // Base case: Visited all cities
totalDist = 0; // return total path distance
for (i = 0; i < cityCnt; ++i) {
printf("%s ", cityNames[currPath[i]]);
if (i > 0) {
totalDist += cityDistances[currPath[i - 1]][currPath[i]];
}
}
printf("= %d\n", totalDist);
else { // Recursive case: pick next city
for (i = 0; i < NUM_CITIES; ++i) {
if (!haveBeen[i]) {
// Add city to travel path
haveBeen[i] = true;
currPath[cityCnt] = toVisit[i];
TravelPaths(currPath, toVisit, haveBeen, cityCnt+1);
// Remove city from travel path
haveBeen[i] = false;
int main(void) {
int* currPath = NULL; // Current path traveled
int* toVisit = NULL; // Cities left to visit
bool* haveBeen = NULL; // City already visited
// Initialize distances array
cityDistances[0][0] = 0;
cityDistances[0][1] = 960; // Boston-Chicago
cityDistances[0][2] = 2960; // Boston-Los Angeles
cityDistances[1][0] = 960; // Chicago-Boston
cityDistances[1][1] = 0;
cityDistances[1][2] = 2011; // Chicago-Los Angeles
cityDistances[2][0] = 2960; // Los Angeles-Boston
cityDistances[2][1] = 2011; // Los Angeles-Chicago
cityDistances[2][2] = 0;
strcpy(cityNames[0], "Boston");
strcpy(cityNames[1], "Chicago");
strcpy(cityNames[2], "Los Angeles");
currPath = (int*)malloc(sizeof(int) * NUM_CITIES);
toVisit = (int*)malloc(sizeof(int) * NUM_CITIES);
haveBeen = (bool*)malloc(sizeof(bool) * NUM_CITIES);
toVisit[0] = 0;
toVisit[1] = 1;
toVisit[2] = 2;
haveBeen[0] = false;
haveBeen[1] = false;
haveBeen[2] = false;
// Explore different paths
TravelPaths(currPath, toVisit, haveBeen, 0);
return 0;
}
Recursive exploration of all possibilities.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
const int TOTAL_NUMS = 3;
void ReorderNums(int* remainNums, int* reorderNums, bool* numAdded, int numCnt) {
int i;
if (numCnt == TOTAL_NUMS) {
for (i = 0; i < numCnt; ++i) {
printf("%d", reorderNums[i]);
printf("\n");
else {
for (i = 0; i < TOTAL_NUMS; ++i) {
if (!numAdded[i]) {
numAdded[i] = true;
reorderNums[numCnt] = remainNums[i];
ReorderNums(remainNums, reorderNums, numAdded, numCnt + 1);
numAdded[i] = false;
}
int main(void) {
int* numsToReorder = NULL;
int* resultNums = NULL;
bool* numAdded = NULL;
numsToReorder = (int*)malloc(sizeof(int) * TOTAL_NUMS);
resultNums = (int*)malloc(sizeof(int) * TOTAL_NUMS);
numAdded = (bool*)malloc(sizeof(int) * TOTAL_NUMS);
numAdded[0] = false;
numAdded[1] = false;
numAdded[2] = false;
numsToReorder[0] = 3;
numsToReorder[1] = 4;
numsToReorder[2] = 5;
ReorderNums(numsToReorder, resultNums, numAdded, 0);
return 0;
}
Cramble from the back
// "New" means new compared to previous level
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
const int TOTAL_NUMS = 3;
void ReorderNums(int* remainNums, int* reorderNums, bool* numAdded,
int numCnt) {
int i;
if (numCnt == TOTAL_NUMS) {
for (i = 0; i < numCnt; ++i) {
printf("%d", reorderNums[i]);
printf("\n");
else {
for (i = TOTAL_NUMS - 1; i >= 0; --i) { // New: This line
changed
if (!numAdded[i]) {
numAdded[i] = true;
reorderNums[numCnt] = remainNums[i];
ReorderNums(remainNums, reorderNums, numAdded, numCnt +
1);
numAdded[i] = false;
int main(void) {
int* numsToReorder = NULL;
int* resultNums = NULL;
bool* numAdded = NULL;
numsToReorder = (int*)malloc(sizeof(int) * TOTAL_NUMS);
resultNums = (int*)malloc(sizeof(int) * TOTAL_NUMS);
numAdded = (bool*)malloc(sizeof(int) * TOTAL_NUMS);
numAdded[0] = false;
numAdded[1] = false;
numAdded[2] = false;
numsToReorder[0] = 1;
numsToReorder[1] = 3;
numsToReorder[2] = 6;
ReorderNums(numsToReorder, resultNums, numAdded, 0);
return 0;
}
challenge activity
7.7.2: Recursive exploration.
Organize the code statements to complete Explore()'s recursive case. The recursive Explore()
function outputs all possible reorderings of an array's elements.
Click here for Explore()'s parameters
Explore() has five parameters:
● Integer array allVals contains the original ordering of the elements.
● Integer array pickedVals contains the elements picked to be part of the current ordering.
● Boolean array inUse contains the in-use status of all the elements in allVals. If the
element in inUse is true, then the corresponding element in allVals has been picked to be
part of the current ordering. Otherwise, the element in allVals has not been picked.
● Integer totalPicked is the number of elements in pickedVals.
● Integer arraySize is the number of elements in allVals.
Base case: When all elements are picked, all the elements are output in the current ordering.
Recursive case: For each element that is not picked yet:
1. Set the element's in-use status to true.
2. Add the element to the end of pickedVals.
3. Call Explore() recursively with the same arguments except that totalPicked is replaced
by totalPicked + 1 to indicate that pickedVals has one more element.
4. Set the element's in-use status back to false.
Recursively output permutations.
#include <stdio.h>
#include <string.h>
// FIXME: Use a static variable to count permutations. Why should the variable be static?
void RemoveFromIndex(char* origString, int remLoc);
void InsertAtIndex(char* origString, char* addChar, int addLoc);
void PermuteString(char* remainLetters, char* permutedLetters) {
char tmpString[2];
int i;
tmpString[1] = '\0';
if (strlen(remainLetters) == 0) { // Base case: All letters used
// FIXME: add count for each permutation
printf("%s\n", permutedLetters);
else { // Recursive case: move a letter from
// remaining to permuted letters
// FIXME: Change loop to output permutations in reverse order
for (i = 0; i < strlen(remainLetters); ++i) {
// Move letter to permuted letters
tmpString[0] = remainLetters[i];
strcat(permutedLetters, tmpString);
RemoveFromIndex(remainLetters, i);
PermuteString(remainLetters, permutedLetters);
// Put letter back in remaining letters
permutedLetters[strlen(permutedLetters) - 1] = '\0';
InsertAtIndex(remainLetters, tmpString, i);
int main(void) {
char wordToPermute[50]; // User defined word to permute.
char finishPermute[50]; // Temp string already permuted.
strcpy(wordToPermute, "");
strcpy(finishPermute, "");
printf("Enter a string to permute (<Enter> to exit): \n");
scanf("%s", wordToPermute);
while (wordToPermute[0] != ' ') {
PermuteString(wordToPermute, finishPermute);
printf("Enter a string to permute (<Enter> to exit): \n");
wordToPermute[0] = ' ';
scanf("%s", wordToPermute);
return 0;
}
// Remove letter at location remLoc from string origString
void RemoveFromIndex(char* origString, int remLoc) {
char tmpString[50]; // Temp string to extract char.
strcpy(tmpString, ""); // Init string
strncat(tmpString, origString, remLoc); // Copy before location remLoc
strncat(tmpString, origString + remLoc + 1,
strlen(origString) - remLoc); // Copy after location remLoc
strcpy(origString, tmpString); // Copy back to original string
// Add letter addChar to location addLoc of string origString
void InsertAtIndex(char* origString, char* addChar, int addLoc) {
char tmpString[50]; // Temp string to add char.
strcpy(tmpString,""); // Init string
strncat(tmpString, origString, addLoc); // Copy before location addLoc
strncat(tmpString, addChar, 1); // Copy letter addChar to location addLoc
strncat(tmpString, origString + addLoc,
strlen(origString) - addLoc); // Copy after location addLoc
strcpy(origString, tmpString);
}
Recursively output permutations (solution).
#include <stdio.h>
#include <string.h>
static int permutationCount; // For counting permutations
void RemoveFromIndex(char* origString, int remLoc);
void InsertAtIndex(char* origString, char* addChar, int addLoc);
void PermuteString(char* remainLetters, // Remaining letters
char* permutedLetters) { // Permuted letters
char tmpString[2];
int i;
tmpString[1] = '\0';
if (strlen(remainLetters) == 0) { // Base case: All letters used
++permutationCount; // Counting permutations
printf("%d) %s\n", permutationCount, permutedLetters);
else { // Recursive case: move a letter from
// remaining to permuted letters
for (i = (strlen(remainLetters) - 1); i >= 0; --i) {
// Move letter to permuted letters
tmpString[0] = remainLetters[i];
strcat(permutedLetters, tmpString);
RemoveFromIndex(remainLetters, i);
PermuteString(remainLetters, permutedLetters);
// Put letter back in remaining letters
permutedLetters[strlen(permutedLetters) - 1] = '\0';
InsertAtIndex(remainLetters, tmpString, i);
int main(void) {
char wordToPermute[50]; // User defined word to permute.
char finishPermute[50]; // Temp string already permuted.
strcpy(wordToPermute, "");
strcpy(finishPermute, "");
printf("Enter a string to permute (<Enter> to exit): \n");
scanf("%s", wordToPermute);
while (wordToPermute[0] != ' ') {
permutationCount = 0;
PermuteString(wordToPermute, finishPermute);
printf("Enter a string to permute (<Enter> to exit): \n");
wordToPermute[0] = ' ';
scanf("%s", wordToPermute);
return 0;
}
// Remove letter at location remLoc from string origString
void RemoveFromIndex(char* origString, int remLoc) {
char tmpString[50]; // Temp string to extract char.
strcpy(tmpString, ""); // Init string
strncat(tmpString, origString, remLoc); // Copy before location remLoc
strncat(tmpString, origString + remLoc + 1,
strlen(origString) - remLoc); // Copy after location remLoc
strcpy(origString, tmpString); // Copy back to original string
// Add letter addChar to location addLoc of string origString
void InsertAtIndex(char* origString, char* addChar, int addLoc) {
char tmpString[50]; // Temp string to add char.
strcpy(tmpString,""); // Init string
strncat(tmpString, origString, addLoc); // Copy before location addLoc
strncat(tmpString, addChar, 1); // Copy letter addChar to location addLoc
strncat(tmpString, origString + addLoc,
strlen(origString) - addLoc); // Copy after location addLoc
strcpy(origString, tmpString);
}
lab activity
7.15.1: LAB: Output a linked list
Write a recursive function called PrintLinkedList() that outputs the
integer value of each node in a linked list. Function PrintLinkedList()
has one parameter, the head node of a list. The main program reads
the size of the linked list, followed by the values in the list. Assume the
linked list has at least 1 node and that all values will be positive.
Ex: If the input of the program is:
5 1 2 3 4 5
the output of the PrintLinkedList() function is:
1, 2, 3, 4, 5,
Hint: Output the value of the current node, then call the
PrintLinkedList() function repeatedly until the end of the list is
reached. Refer to the IntNode class to explore any available member
functions that can be used for implementing the PrintLinkedList()
function.
#include <stdio.h>
#include "IntNode.h"
/* TODO: Write recursive PrintLinkedList() function here. */
// Create a new node
IntNode_struct* CreateNode(int value) {
IntNode_struct* newNode =
(IntNode_struct*)malloc(sizeof(IntNode_struct));
newNode->dataVal = value;
newNode->nextNodePtr = NULL;
return newNode;
int main(void) {
int size;
int value;
scanf("%d", &size);
IntNode_struct* headNode = CreateNode(-1); // Make head node as the
first node
IntNode_struct* lastNode = headNode; // Node to add after
IntNode_struct* newNode = NULL; // Node to create
// Insert the second and the rest of the nodes
for (int n = 0; n < size; ++n) {
scanf("%d", &value);
newNode = CreateNode(value);
IntNode_InsertAfter(lastNode, newNode);
lastNode = newNode;
// Call PrintLinkedList() with node after head node
//PrintLinkedList(IntNode_GetNext(headNode));
return 0;