//scroll down to look
//answer goes down here
Force us n00bs to think in algorithms (and better code)
Gage64 has been doing something similar on another thread, but I figured we may as well have an official thread on it.
So please hit us with algorithms which will make us write 20 lines of code to only show us that it can be done in 5 (without STL).
Two that have already been done are: Break down a number (ie. 2346 as 2, 3, 4, 6) and Palindrome check.
please post your answer using code using [source][/source] tags
example:
[Edited by - Alpha_ProgDes on July 6, 2008 1:29:40 AM]
Continuing with the theme of manipulating numbers: write a function that counts from 1 to MAX but only prints numbers whose digits do not repeat. For example, part of the output would contain 8, 9, 10, 12 (11 is invalid) then later 98, 102, 103 (99, 100, 101 are invalid). Borrowed from Cedric; the linked post has a lengthy and interesting discussion of potential solutions.
Calculate if two numbers are digital permutations of each other, in other words if they have the same digits but in different order. For example 1124 and 1214 respect this condition while 1734 and 9628 no.
Edit: There is a quite easy algorithm that use two loops here, can you find one with a single loop?
Edit: There is a quite easy algorithm that use two loops here, can you find one with a single loop?
Doing a google search for "programming exercises" give some interesting results, like this one.
A while ago I thought about posting some introductory programming problems but wasn't sure how useful it would be (given the already available resources out there), but for anyone interested, here they are (work in progress):
1. Variables and Expressions
1.1. Write a program that accepts the width and height of a rectangle and returns the area and perimiter.
1.2. Write a program that has two variables with initial values, and add code that causes the values in the variables to be swapped. That is, if you have the variables: a, b, then after the code is executed, the value of a will equal the initial value of b, and the value of b will equal to the initial value of a.
1.3. Write a program that accepts a positive two digit number and writes the two digits of the number, separated by a space.
1.4. Write a program that accepts two numbers, a and b, and writes a random number in the range [a, b] (that is, the range should be inclusive).
2. Conditionals
2.1. Write a program that accepts two numbers as input and prints the bigger number.
2.2. Repeat 2.1 with 3 numbers.
3. Loops
Note - you should not use an array to solve any of the exercises in this section.
3.1. Write a program that reads 10 numbers and writes their average.
3.2. Write a program that reads a sequence of numbers and writes their average. the sequence ends when the number -1 is read (and -1 should not participate in the calculation of the average).
3.3. Write a program that reads a positive number and prints the sum of it's digits. For example, if the number is 327, the output should be 12.
3.4. Write a program that reads a positive number and writes it with the digits reversed. For example, if the number is 327, the output should be 723.
3.5. Write a program that reads a sequence of numbers. The sequence ends when -1 is read. The program should write the largest of the numbers entered.
3.5. Like to 3.5, but this time also write the second largest number entered. Test your program with various inputs to make sure it's correct.
3.6. Write a program that reads a number, and prints rows of '*'. For example, if the number is 4, the output should be:
*
**
***
****
3.7. Like 3.6, but this time if the number is 4, the output should be:
*
***
*****
*******
3.8. Write a program that reads a number and simply prints it. However, if the number is less than 100, the program should display an error message and request input again. That is, the program should only end when valid input is entered.
4. Arrays
4.1. Write a program that reads 10 numbers and writes all numbers that are greater than the average of the numbers.
4.2. Write a program that reads 10 numbers and writes the numbers in reverse order.
4.3. Write a program that reads grades between 0-100 (the program should accept only grades in that range). The program should stop reading when -1 is entered. The program should print a table showing how many times each grade was entered. For example, if the input is: 60, 75, 60, 80, 75, 75, -1, the output should look something like:
60 - 2
75 - 3
80 - 1
Note that the output does not need to be sorted in any way.
4.4. Write a program that reads 10 numbers and puts them in an array. The program should print all numbers whose value is exactly twice the value of it's array index. For example, if array[3] has a value of 6, then 6 should be printed.
5. Functions
5.1. Write a game where the user has to guess a string. Initially, a '*' should be displayed for each letter. Each time the user guesses a letter, that letter should be displayed. The game is over when the user guesses the string.
A sample output should look something like this:
***
Enter a letter: g
g is not in the string.
***
Enter a letter: a
Correct!
*a*
Enter a guess: C
Correct!
Ca*
Enter a guess: n
n is not in the string.
Ca*
Enter a guess: t
Correct!
You guessed it! The string was: Cat.
5.2. Make the following modifications to 5.1:
a) Count the number of tries it took the user to guess the whole string.
b) At each round, give the user an option to guess the entire string.
5.3. Write a function that accepts two strings as parameters. If the second string is part of the first, the function should return the index at which the second string begins within the first. Otherwise, it should return -1.
For example, if the first string is "hello World!" and the second string is "lo", the function should return 3.
Not all of these are necessarily very "algorithmic" in nature, but they do develop the type of thinking that is useful to a programmer. Also, most (if not all) of them can be solved "elegantly", so if your solution feels convoluted or unnaturally long, there's probably a better way.
This list is also not very exhaustive (many topics are missing), but hopefully other people will add to it over time. Maybe this thread can even become a sticky...
A while ago I thought about posting some introductory programming problems but wasn't sure how useful it would be (given the already available resources out there), but for anyone interested, here they are (work in progress):
1. Variables and Expressions
1.1. Write a program that accepts the width and height of a rectangle and returns the area and perimiter.
1.2. Write a program that has two variables with initial values, and add code that causes the values in the variables to be swapped. That is, if you have the variables: a, b, then after the code is executed, the value of a will equal the initial value of b, and the value of b will equal to the initial value of a.
1.3. Write a program that accepts a positive two digit number and writes the two digits of the number, separated by a space.
1.4. Write a program that accepts two numbers, a and b, and writes a random number in the range [a, b] (that is, the range should be inclusive).
2. Conditionals
2.1. Write a program that accepts two numbers as input and prints the bigger number.
2.2. Repeat 2.1 with 3 numbers.
3. Loops
Note - you should not use an array to solve any of the exercises in this section.
3.1. Write a program that reads 10 numbers and writes their average.
3.2. Write a program that reads a sequence of numbers and writes their average. the sequence ends when the number -1 is read (and -1 should not participate in the calculation of the average).
3.3. Write a program that reads a positive number and prints the sum of it's digits. For example, if the number is 327, the output should be 12.
3.4. Write a program that reads a positive number and writes it with the digits reversed. For example, if the number is 327, the output should be 723.
3.5. Write a program that reads a sequence of numbers. The sequence ends when -1 is read. The program should write the largest of the numbers entered.
3.5. Like to 3.5, but this time also write the second largest number entered. Test your program with various inputs to make sure it's correct.
3.6. Write a program that reads a number, and prints rows of '*'. For example, if the number is 4, the output should be:
*
**
***
****
3.7. Like 3.6, but this time if the number is 4, the output should be:
*
***
*****
*******
3.8. Write a program that reads a number and simply prints it. However, if the number is less than 100, the program should display an error message and request input again. That is, the program should only end when valid input is entered.
4. Arrays
4.1. Write a program that reads 10 numbers and writes all numbers that are greater than the average of the numbers.
4.2. Write a program that reads 10 numbers and writes the numbers in reverse order.
4.3. Write a program that reads grades between 0-100 (the program should accept only grades in that range). The program should stop reading when -1 is entered. The program should print a table showing how many times each grade was entered. For example, if the input is: 60, 75, 60, 80, 75, 75, -1, the output should look something like:
60 - 2
75 - 3
80 - 1
Note that the output does not need to be sorted in any way.
4.4. Write a program that reads 10 numbers and puts them in an array. The program should print all numbers whose value is exactly twice the value of it's array index. For example, if array[3] has a value of 6, then 6 should be printed.
5. Functions
5.1. Write a game where the user has to guess a string. Initially, a '*' should be displayed for each letter. Each time the user guesses a letter, that letter should be displayed. The game is over when the user guesses the string.
A sample output should look something like this:
***
Enter a letter: g
g is not in the string.
***
Enter a letter: a
Correct!
*a*
Enter a guess: C
Correct!
Ca*
Enter a guess: n
n is not in the string.
Ca*
Enter a guess: t
Correct!
You guessed it! The string was: Cat.
5.2. Make the following modifications to 5.1:
a) Count the number of tries it took the user to guess the whole string.
b) At each round, give the user an option to guess the entire string.
5.3. Write a function that accepts two strings as parameters. If the second string is part of the first, the function should return the index at which the second string begins within the first. Otherwise, it should return -1.
For example, if the first string is "hello World!" and the second string is "lo", the function should return 3.
Not all of these are necessarily very "algorithmic" in nature, but they do develop the type of thinking that is useful to a programmer. Also, most (if not all) of them can be solved "elegantly", so if your solution feels convoluted or unnaturally long, there's probably a better way.
This list is also not very exhaustive (many topics are missing), but hopefully other people will add to it over time. Maybe this thread can even become a sticky...
I think having a sub-forum for Project Euler challenges which would let us share solutions/hints on solving different challenges would be pretty cool, but then again if we all showed solutions then whats stopping anyone from just copying the answers :(
Gage64 Challenges:
Challenge 1.1
Challenge 1.2
Challenge 1.3
Challenge 1.4
Challenge 2.1
Challenge 2.2
I'll leave it at that, it's starting to take up a bit of space, maybe I should of used a pastebin ><
[Edited by - cNoob on July 6, 2008 3:19:23 AM]
Gage64 Challenges:
Challenge 1.1
#include <iostream>int main(){ int width, height; std::cout << "Enter rectangle width: "; std::cin >> width; std::cout << "Enter rectangle height: "; std::cin >> height; std::cout << "Rectangles area = " << width * height << std::endl; std::cout << "Rectangles Perimiter = " << (width*2)+(height*2) << std::endl; return 0;}Challenge 1.2
#include <iostream>void Swap(int &a, int &b){ int tmp = a; a = b; b = tmp;}int main(){ int a = 5, b = 3; Swap(a, b); std::cout << "a = " << a << ", b = " << b << std::endl; return 0;}Challenge 1.3
#include <iostream>int main(){ int number = 0; int tens = 0, units = 0; while(number < 10 || number > 99) { std::cout << "Enter a 2 Digit Number: "; std::cin >> number; } tens = number / 10; units = number % 10; std::cout << "Tens = " << tens << ", Units = " << units << std::endl; return 0;}Challenge 1.4
#include <iostream>#include <time.h>int RandomFromRange(int min, int max){ int r = rand()%(max-min); return r+min;}int main(){ srand(time(NULL)); int min = 0, max = 0; std::cout << "Enter a number: "; std::cin >> min; while(max <= min) { std::cout << "Enter a number greater than " << min << ": "; std::cin >> max; } std::cout << "Random number between " << min << " and " << max << ": " << RandomFromRange(min, max) << std::endl; return 0;}Challenge 2.1
#include <iostream>int main(){ int a = 0, b = 0; std::cout << "Enter a number: "; std::cin >> a; std::cout << "And another number: "; std::cin >> b; if(a > b) std::cout << a << " was the highest number"; else if(a < b) std::cout << b << " was the highest number"; else std::cout << "Both numbers are equal"; return 0;}Challenge 2.2
#include <iostream>int main(){ int numbers[3] = {0, 0, 0}; std::cout << "Enter a number: "; std::cin >> numbers[0]; std::cout << "And another number: "; std::cin >> numbers[1]; std::cout << "Just one more number: "; std::cin >> numbers[2]; if(numbers[0] > numbers[1] && numbers[0] > numbers[2]) std::cout << numbers[0] << " was the highest number"; else if(numbers[1] > numbers[0] && numbers[1] > numbers[2]) std::cout << numbers[1] << " was the highest number"; else if(numbers[2] > numbers[0] && numbers[2] > numbers[1]) std::cout << numbers[2] << " was the highest number"; else std::cout << "All 3 numbers are equal"; return 0;}I'll leave it at that, it's starting to take up a bit of space, maybe I should of used a pastebin ><
[Edited by - cNoob on July 6, 2008 3:19:23 AM]
Here's a fiddly one:
Write a program that will print out any given integer in binary form, for example:
> 10
< 1010
the numeral 10 would print out as "1010". Note that the order of binary digits printed matters. Don't use the STL if you can help it. See if it works for negative numbers as well.
My terrible 5-line solution (well, 4 lines really):
I'd love to see a more elegant solution to this.
Write a program that will print out any given integer in binary form, for example:
> 10
< 1010
the numeral 10 would print out as "1010". Note that the order of binary digits printed matters. Don't use the STL if you can help it. See if it works for negative numbers as well.
My terrible 5-line solution (well, 4 lines really):
I'd love to see a more elegant solution to this.
void toBinary(int number){ int i = sizeof(int) * 8; while (--i >= 0) { int mask = (0x1 << i); std::cout << ((number & mask) >> i); } std::cout << "\n";}Quote:Original post by errcw
Continuing with the theme of manipulating numbers: write a function that counts from 1 to MAX but only prints numbers whose digits do not repeat. For example, part of the output would contain 8, 9, 10, 12 (11 is invalid) then later 98, 102, 103 (99, 100, 101 are invalid). Borrowed from Cedric; the linked post has a lengthy and interesting discussion of potential solutions.
Here is my rather lengthy solution
[Source]static int Check(int a, int b, int c) { if ((a == b) || (a == c) || (b == c)) return 1; else return 0; } static int Check(int a, int b) { if (a == b) return 1; else return 0; } static int CheckNumbers(int a) { int value = a; int[] temp = new int[3]; if (a < 11) return 0; if ((a > 10) && (a < 100)) { temp[0] = a % 10; a = a / 10; temp[1] = a % 10; a = a / 10; if (Check(temp[0], temp[1]) == 1) return 1; } if (a > 99) { temp[0] = a % 10; a = a / 10; temp[1] = a % 10; a = a / 10; temp[2] = a % 10; if (Check(temp[0], temp[1], temp[2]) == 1) return 1; } return 0; } static void Main(string[] args) { int i; int value; value = 1 / 10; Console.WriteLine(value); Console.Write("Enter the number -> to count : "); value = Convert.ToInt32(Console.ReadLine()); for(i=1;i<=value;i++) if(CheckNumbers(i)!=1) Console.Write("{0}, ", i); Console.ReadLine(); }[/Source]
@PCosmin89: Why are you using an int instead of a bool for the return type?
Also, your solution doesn't work for numbers greater than 999. Try to write a general solution that will work regardless of how many digits the number has.
Also, your solution doesn't work for numbers greater than 999. Try to write a general solution that will work regardless of how many digits the number has.
Quote:Original post by errcw
Continuing with the theme of manipulating numbers: write a function that counts from 1 to MAX but only prints numbers whose digits do not repeat. For example, part of the output would contain 8, 9, 10, 12 (11 is invalid) then later 98, 102, 103 (99, 100, 101 are invalid). Borrowed from Cedric; the linked post has a lengthy and interesting discussion of potential solutions.
Here's my solution:
/*Here I use a bit mask to keep track of digits seen. The least significant bit keeps track of the digit 0, next significant bit keeps track of digit 1, etc. Thus when we scan through each digit, we set the appropriate bit in the mask.If the bit is already set, then that indicates that the digit has been seen before in the number. The process is repeated for each number 0 .. MAX*/#include <iostream>bool shouldPrint(int number){ int bitmask = 0x0; while (number != 0) { int r = number % 10; if ((bitmask & (0x1 << r)) >> r) return false; else bitmask |= (0x1 << r); number /= 10; } return true;}int main(int argc, char** argv){ int max = 0; std::cin >> max; for (int i = 0; i <= max; ++i) { if (shouldPrint(i)) std::cout << i << " "; } std::cout << "\n";}Quote:Original post by KMD
Here's a fiddly one:
Write a program that will print out any given integer in binary form, for example:
> 10
< 1010
*** Source Snippet Removed ***
uhh, your code always prints out 32 bits (or 64)
3 lines according to your standard, and only prints out the necessary bits, and still printing '0' for zero =)
void toBinary(int number){ do { std::cout << (number & 1); } while ((number >>= 1) != 0); std::cout << "\n";}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
