Sign in to follow this  
Alpha_ProgDes

Force us n00bs to think in algorithms (and better code)

Recommended Posts

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:
//scroll down to look


























//answer goes down here

[Edited by - Alpha_ProgDes on July 6, 2008 1:29:40 AM]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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

















#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]

Share this post


Link to post
Share on other sites
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.




















void toBinary(int number)
{
int i = sizeof(int) * 8;
while (--i >= 0)
{
int mask = (0x1 << i);
std::cout << ((number & mask) >> i);
}
std::cout << "\n";
}



Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
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";
}




Share this post


Link to post
Share on other sites
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";
}



Share this post


Link to post
Share on other sites
[quote]Original post by Gage64[quote]

A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms. However, since C++ is unnecessarily verbose, I'll be using OCaml instead as an illustration of the algorithms:

// Scroll down 
















// 1.1. Write a program that accepts the width and height of a rectangle and
// returns the area and perimiter.

let rectangle width height =
width * height, (width + height) * 2

// 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.

let swap (a,b) =
(b,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.

let split num =
Printf.sprintf "%d %d" (num / 10) (num mod 10)

// 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).

let interval a b =
Random.int (b - a + 1) + a

// 2.1. Write a program that accepts two numbers as input and prints the bigger number.

let bigger a b =
max a b

// 2.2. Repeat 2.1 with 3 numbers.

let biggest a b c =
max a (max b c)

// 3.1. Write a program that reads 10 numbers and writes their average.

let avg f =
let rec aux tot = function
| 10 -> tot / 10
| n -> aux (tot + f()) (n+1)
in aux 0 0

// 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).

let avg f =
let rec aux tot n =
match f () with
| -1 -> tot / n
| x -> aux (tot + x) (n + 1)
in aux 0 0

// 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.

let rec sum = function
| 0 -> 0
| n -> n mod 10 + sum (n/10)

// 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.

let rec rev = function
| 0 -> ""
| n -> string_of_int (n mod 10) ^ rev (n / 10)

// 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.

let best f =
let rec aux best =
match f () with
| -1 -> best
| x -> aux (max best x)
in aux min_int

// 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.

let best2 f =
let rec aux (fst,snd) =
match f () with
| -1 -> (fst,snd)
| x -> aux (max fst x, max (min fst x) snd)
in aux (min_int, min_int)

// 3.6. Write a program that reads a number, and prints rows of '*'. For example, if
// the number is 4, the output should be:
//
// *
// **
// ***
// ****

let lines n =
let rec aux lst = function
| 0 -> lst
| n -> lst ^ "\n" ^ aux (lst ^ "*") (n - 1)
in aux "" n

// 3.7. Like 3.6, but this time if the number is 4, the output should be:
//
// *
// ***
// *****
// *******

let lines n =
let rec aux lst = function
| 0 -> lst
| n -> lst ^ "\n" ^ aux (if lst = "" then "*" else lst ^ "**") (n - 1)
in aux "" n

// 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.

let rec read_until f =
match f () with
| bad when bad < 100 -> print_endline "bad input"; read_until f
| good -> good

// 4.1. Write a program that reads 10 numbers and writes all numbers that are greater
// than the average of the numbers.

let bigger lst =
let avg = List.fold_left (+) 0 lst / List.length lst in
List.filter ( (>) avg ) lst

// 4.2. Write a program that reads 10 numbers and writes the numbers in reverse order.

let rev lst =
let rec aux rv = function
| [] -> rv
| h::t -> aux (h::rv) t
in aux [] lst

// 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

let totals f =
let data = Array.make 100 0 in
let rec read () =
match f () with
| -1 -> ()
| x when x < 100 && x >= 0 -> data.(x) <- data.(x) + 1; read ()
| x -> read ()
in read ();
Array.iteri (fun i x -> if x > 0 then Printf.printf "%d - %d\n" i x) data

// 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.

let print_if_double arr =
Array.iteri (fun i x -> if x = i * 2 then Printf.printf "%d " x) arr


Now, a few other interesting questions on the algorithmic side:

  1. Given a sequence of integers, find the median of these integers in linear time complexity.

  2. Given a function f which represents an unknown equivalence relationship between the integers [1, 100], find in linear time complexity whether one of the equivalence classes contains more than half of the elements of the interval.

  3. The White Wolf probability system: you throw N 10-sided dice, compute the probability that at least T dice will be higher than D, as a function of (N,T,D).

  4. You are given an incomplete order relationship over [1, N], given as a list of (i,j) pairs where i < j. Sort [1, N] according to that order (if elements are not comparable, you may place them in any order).

  5. You are given a flattened directory tree: a sequence of elements of the form (name, depth) where the folder itself always appears directly above its elements. Build and return the corresponding directory tree.

Share this post


Link to post
Share on other sites
Quote:
Original post by apatriarca
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?


Oh wait, maybe i shouldn't be answering, i'm not a n00b ;)

Two loop solution, I can't think of a 1 loop solution yet. also it's not code, just the method, cause I'm lazy...

//scroll down to look




















First loop decompose the numbers like in the link in the first post, doing basically a radix sort with digits from one number being +1, and other being -1,

if they use the same digits, the second loop will check that radix sort array will be all 0s


Share this post


Link to post
Share on other sites
Quote:
Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????


The Cormen-Leiserson-Rivest-Stein "Introduction to Algorithms" book is intended for beginners, and allows to solve (if it doesn't solve them as an example) exercises 1, 4 and 5. Question 2 is a trick question that relies on wit rather than algorithmic knowledge, so beginners and experienced developers should have the same difficulties if they don't know it yet. As for question 3, a non-optimal recursive solution can be derived from the mathematical definition with extreme simplicity (with the optimal solution being based on dynamic programming applied to the non-optimal solution).

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms.


You're right. They were intended to test your understanding of fundamental programming constructs, so maybe this isn't the best thread for them, but what's done is done.

Quote:
Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????


QFE. Not many beginners are likely to be familiar with O'Caml.

Share this post


Link to post
Share on other sites
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.


edit: appears to be already answered using basically the same solution above... *sigh*


















void count(int max)
{
for (int i = 0; i <= max; ++i)
if (validate(i))
std::cout << i << endl;
}

bool validate(int number)
{
int map = 0; // must be on a platform where int > 10 bits...

do
{
int digit = number % 10;

if (map & (1 << digit) != 0)
return false;
map |= 1 << digit;

} while ((number /= 10) != 0)

return true;
}






[Edited by - Axiverse on July 6, 2008 4:01:16 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Axiverse
Quote:
Original post by apatriarca
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?


Oh wait, maybe i shouldn't be answering, i'm not a n00b ;)

Two loop solution, I can't think of a 1 loop solution yet. also it's not code, just the method, cause I'm lazy...

*** Source Snippet Removed ***

You are almost there. But you have to find a method to verifies the last condition without using a loop (you can check that efficiently while executing the first loop).

Share this post


Link to post
Share on other sites
Quote:
Original post by Axiverse
3 lines according to your standard, and only prints out the necessary bits, and still printing '0' for zero =)

*** Source Snippet Removed ***


Unfortunately, your code snippet prints out the bits in reverse order. And it does not work for negative numbers. Otherwise that solution would have been perfect, maybe theres a way to reverse order that it prints?

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by Alpha_ProgDes
Uhhh, ToohrVyk.... you realize this is for beginners????


The Cormen-Leiserson-Rivest-Stein "Introduction to Algorithms" book is intended for beginners


I think this thread is meant for someone relatively new to programming (as it has "n00bs" in the title). That book requires a fairly solid understanding of fundamental programming constructs, as well as familiarity with some math topics (probably discrete mathematics or something similar). I wouldn't call someone with that knowledge a n00b.

Still, I'm sure many people will enjoy the challenge.

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
Quote:
Original post by ToohrVyk
A nice set of exercises, although thy insist more on imperative programming techniques than on actual algorithms.


You're right. They were intended to test your understanding of fundamental programming constructs, so maybe this isn't the best thread for them, but what's done is done.

If we're talking about programming techniques such as: pimpl, factories, splitting interface and implementation, avoiding if statements in while loops, then maybe we should have a separate thread for that as well [smile]

If that's not what you meant by imperative programming techniques, please correct me.

Share this post


Link to post
Share on other sites
ops about that backwards output, hmm... okay, well i'm not a complete n00b XD

i still don't see how you can check if the digits even out to zero in the first loop as that one is dependent on the length of the number. oooh, i got it, you can use a bitmap for zero'd digits, or a count for the number of non-zero'd digits in the first loop and then check if it's zero at the end.

though somehow i feel there's a more elegent way.

edit: on the binary output, it can work with negative numbers with a simple change
while ((*(unsigned int*)(&number) >>= 1) != 0);

but still backwards... i'll think about it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
I think this thread is meant for someone relatively new to programming (as it has "n00bs" in the title). That book requires a fairly solid understanding of fundamental programming constructs, as well as familiarity with some math topics (probably discrete mathematics or something similar). I wouldn't call someone with that knowledge a n00b.


I would have to disagree. The entire Chapter 1 is dedicated to explaining what an algorithm is, while section 1 of Chapter 2 introduces arrays, loops, conditionals and assignment without requiring any prior knowledge. There is certainly a small prerequisite in mathematics (such as for complexity analysis) but it doesn't play a heavy role in the first few chapters outside of algorithm analysis. In any event, if someone wanted to start computer science without any computer-related prior knowledge, the CLRS' Introduction to Algorithms is the first book I would suggest.

Share this post


Link to post
Share on other sites
Quote:
Original post by Axiverse
ops about that backwards output, hmm... okay, well i'm not a complete n00b XD

i still don't see how you can check if the digits even out to zero in the first loop as that one is dependent on the length of the number. oooh, i got it, you can use a bitmap for zero'd digits, or a count for the number of non-zero'd digits in the first loop and then check if it's zero at the end.

though somehow i feel there's a more elegent way.

I don't know if there is an elegant solution for this. The following is the solution I had in mind, your solutions probably works too. My brother had to solve a similar problems in one of his exams. The professor added the single loop condition but he then ignored it. His solution actually had 3 loops because he calculates the length of the string (the test was on strings...) before doing the two loops.


//scroll down to look


























I have decided to maintain the sum of the squares of the numbers. The sum of the squares of the numbers is zero only if all the numbers are zeros. Suppose I have the sum S = A + b^2 and I want to calculate S' = A + (b+1)^2.
S' = A + b^2 +2b + 1 = S + 2*b + 1
So I can calculate the new value of the sum of squares adding 2 times the current number.
The same can be done when I want to subtract one to one of the numbers:
S' = A + (b-1)^2 = A + b^2 -2b + 1 = S - 2b + 1

The bitmap solution can be faster than this method, but it wasn't applicable with strings. My brothers have written a solution similar to the one I have previously presented but summing the absolute values of the numbers. All of these methods are valid.


Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
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.


[Source]



















//3.1
static void Average()
{
int i, value, average = 0, counter = 0;

for (i = 1; i <= 10; i++)
{
value = Convert.ToInt32(Console.ReadLine());
average = average + value;
counter++;
}

Console.WriteLine("The average is: {0};", average / counter);
Console.ReadLine();
}

//3.2
static void ArrayAverage()
{
int i, value, average = 0, counter = 0;

for (i = 1; ; i++)
{
value = Convert.ToInt32(Console.ReadLine());
if (value == -1)
break;
average = average + value;
counter++;
}

Console.WriteLine("The average is: {0};", average / counter);
Console.ReadLine();
}

//3.3
static void DigitSum()
{
int number, sum = 0, temp;
Console.Write("What is the number: "); number = Convert.ToInt32(Console.ReadLine());
while (number != 0)
{
temp = number % 10;
sum = sum + temp;
number = number / 10;
}
Console.WriteLine(sum);
Console.ReadLine();
}

//3.4
static void ReverseNumber()
{
int number;
Console.Write("What is the number: "); number = Convert.ToInt32(Console.ReadLine());
while (number != 0)
{
Console.Write(number % 10);
number = number / 10;
}
Console.ReadLine();
}

//3.5
static void LargestNumber()
{
int i, value, temp = 0;

for (i = 1; ; i++)
{
value = Convert.ToInt32(Console.ReadLine());
if (value == -1)
break;
if (value > temp)
temp = value;
}

Console.WriteLine(temp);
Console.ReadLine();
}

//3.5.2
static void SecondLargestNumber()
{
int i, value, temp = 0, temp2 = 0;

for (i = 1; ; i++)
{
value = Convert.ToInt32(Console.ReadLine());
if (value == -1)
break;
if (value > temp)
temp = value;
if (( value < temp ) && (value > temp2))
temp2 = value;
}

Console.WriteLine(temp);
Console.WriteLine(temp2);
Console.ReadLine();
}
[/Source]


Criticism is appreciated :)

Share this post


Link to post
Share on other sites
Quote:
Original post by PCosmin89
Criticism is appreciated :)


This may contain potential "spoilers" (for others), so scroll down if you want to take a look.



















// 3.1
//There's no need for the counter. You already know how many numbers there are.

// 3.5.2 (and some others)
// Give variables meaningful names (i.e., max instead of temp)

// Declare variables only when you need them and can initialize them:
for (int i = 1; ...)

// Aside from that, you can use another type of loop to make this more elegant.





EDIT: The following refers to the solution for 3.5.2 only.
Now the non-spoiler comment: It doesn't work. [smile]

This question is a bit tricky and that's why I said you should test it with various types of input. Try to come up with a series of numbers that will give an incorrect answer.

[Edited by - Gage64 on July 6, 2008 7:30:56 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this