Week 1 - C
Welcome to CS50! This is Week 1 and I will be going to talk about my summary of Week 1's content.
Problem Set 1
This problem serves as the beginning of this course. Welcome to CS50!
Things to notice in the problem statement:
"Re-prompt the user, again and again as needed, if their input is not greater than 0 or not an int altogether."
Divide and Conquer
Procedure Main
Prompt the user for the pyramid's height
For each row from 1 to height
Call PrintRow for the current row
End For
End Procedure
Procedure PrintRow(rowNumber, height)
Print (height - rowNumber) spaces
Print (rowNumber + 1) bricks
End ProcedureUseful Snippets
Prompt the user until the input is valid.
// do-while loop
int n;
do
{
n = get_int("Height: ");
}
while (n < 1);Make the pyramid right-aligned
void print_row(int bricks, int total)
{
int i;
// Print whitespace
for (i = 0; i < total - bricks; i++)
printf(" ");
// Print bricks
for (j = 0; j < bricks; j++)
printf("#");
printf("\n");
}Take-aways
Use
do-while loopto prompt until the input is valid.Divide the problem into smaller parts by finding the patterns, just keep in mind if something is duplicate in your program, then it's likely to have a more compact way to do that.
Using the same settings from the problem above, now the bricks pattern we want to print is different. But, we can still using the design structure and the only thing we need to change is the print_row() function.
Useful Snippets
Change the
print_rowfunction to meet our requirements
void print_row(int bricks, int total)
{
int i;
// Print white spaces at the left
for (i = 0; i < total - bricks; i++)
printf(" ");
// Print bricks at the left
for (i = 0; i < bricks; i++)
printf(" ");
// Print the middle white space
printf(" ");
// Print the bricks at the right
for (i = 0; i < bricks; i++)
printf("#");
// End
printf("\n");
}Take-aways:
In this hard version of Mario, we can clearly see the importance of finding a good "structure" to solve a problem. Since this good structure can be reused, which will make our code flexible. And one way to make your code flexible is to write good functions.
Before the problem
There are only four types of cents:
1(pennies),5(nickles),10(dimes),25(quarters)Introduction to Greedy Algorithm A greedy algorithm is one “that always takes the best immediate, or local, solution while finding an answer. Due to this characteristic, greedy algorithm can find the overall optimal solution of an optimization problem, but sometimes it may find less-than-optimal solutions.
Things to notice in the problem statement
Reprompt the user until the input is valid.
Divide and Conquer
Use Greedy algorithm to understand the problem. Given an initial owing (a certain number), we always try the first biggest cent until the remaining owing is smaller than this biggest-first cent. Then we move on to the secondest cent until the owing is 0. (Since our smallest cent is
1, which means we can always find a solution to this problem)Design our structure
Procedure Main
Prompt the user for change owed (in cents)
Calculate the number of quarters to give the customer
Subtract the value of those quarters from cents
Calculate the number of dimes to give the customer
Subtract the value of those dimes from cents
Calculate the number of nickels to give the customer
Subtract the value of those nickels from cents
Calculate the number of pennies to give the customer
Subtract the value of those pennies from cents
End ProcedureUseful snippets
Implement the calculation using a specific function
int calculate_quarters(int cents)
{
int quarters = 0;
while (cents >= 25)
{
quarters++;
cents = cents - 25;
}
return quarters;
}Take-aways
The idea of greedy algorithm and its application.
If we use greedy algorith, we must update our parameter for the next greedy use.
Before the problem
Luhn's Algorithm: This algorithm is used to check whether a credit card is valid or not by using a checksum. The procedure of this algorithm is below:
Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
Add the sum to the sum of the digits that weren’t multiplied by 2.
If the total’s last digit is 0 (or, put more formally, if the total modulo 10 is congruent to 0), the number is valid! Notice that sometimes hackers will take use of this property, so we still need to look through the database to make sure whether the credit card number is valid or not.
Things to notice in the problem statement
The input should be
long
Divide and Conquer
Procedure Main
For each digit in the number
Calculate the checksum
Get the length of the number
End For
Calculate the first and second digits of the number
Determine the type of the credit card
End ProcedureUseful Snippets
One
whileloop version
// Define and Initialize the variables
long num_copy = num;
int digit, sum1, indicator, length;
indicator = 0;
length = 0;
sum1 = 0;
// Calculate sum and length
while (num != 0) {
digit = num % 10;
if (indicator)
{
int temp = digit * 2;
if (temp >= 10)
{
while (temp)
{
sum1 += temp % 10;
temp /= 10;
}
}
else
{
sum1 += temp;
}
indicator = 0;
}
else
{
sum1 += digit;
indicator = 1;
}
length++;
num /= 10;
}Calculate the first and second digit: We have two methods to implement this, which are shown as follows:
Method 1
int first_digit = num_copy / pow(10, length - 1);
int second_digit = (num_copy - first_digit * pow(10, length - 1)) / pow(10, length - 2);In this method, we will use the length of the number.
Method 2
while (num < 100) {
num /= 10;
}
first_digit = num / 10;
second_digit = num % 10;In this method, we divide the number until the num is smaller than 100. And the remaining number is composed by the first and second digit.
Take-aways
num % 10will get the last digit of a number.num / 10will discard the last digit if num is an integer(includingintandlong).
Last updated