designing algorithms

This is a discussion on designing algorithms within the C# Programming forums, part of the General Programming Boards category; this code below has been copied and annotated from the C++ section, Code: using System; class Test { static void ...

  1. #1
    budding software engineer luigi40's Avatar
    Join Date
    Jun 2004
    Location
    South Coast UK
    Posts
    61

    designing algorithms

    this code below has been copied and annotated from the C++ section,

    Code:
    using System;
    
    
    class Test
    {
    	 
    	
    	
    	static void Main(string[] args)
    	{
    		int t, space, star; 
    			int outer=5;//set final value of control variable 
    
    			//top of diamond - outer loop
    			for (t = 1; t <= outer; t++)//control variable t active while  
    			{							//less than or equal to outer
    				for (space = outer; space >= t; space--)//set control variable 
    					Console.Write(' ');//space to outer value
    				//while space is greater/or equal to t print space
    				for (star = 1; star <= (t * 2 - 1); star++)
    					Console.Write('*');
    					Console.WriteLine();
    			}
    			
    		
    			//bottom of diamond
    			for (t = 1; t <= outer - 1; t++)
    			{
    				for (space = 1; space <= t + 1; space++)//while control variable 
    					Console.Write(' ');//space is less than or equal to outer 
    									   //control var t + 1 print space
    				for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1
    					Console.Write('*');
    				Console.WriteLine();
    			}
    			
    	}
    	
    }
    this program prints a diamond shape, my question is how does one work out the these 2 loops

    Code:
    for (star = 1; star <= (t * 2 - 1); star++)
    	Console.Write('*');
    	Console.WriteLine();
    
    
    for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1
    	Console.Write('*');
    	Console.WriteLine();
    previous to seeing this code i had written down a simple flowchart depicting all different stages for each line, as well writing out the sequence of numbers for stars and spaces. is it purely a maths calculation to work out the line...
    Code:
    for (star = 1; star <= outer * 2 - (t * 2 + 1); star++)//7, 5, 3, 1
    or is there a method to this ?

    i would have taken forever to get to this without seeing this code, i guess some people are quick problem solvers or they have solved many similar problems

    what are your thoughts?
    Last edited by luigi40; 11-22-2005 at 01:14 PM.

  2. #2
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    There's many ways to print a diamond. Consider a diamond with a "radius" of 2:
    Code:
      *      radius of 2
     *** 
    *****
     *** 
      *
    The next step I took to create an algorithm was to note the coordinates of each spot where a * was printed:
    Code:
            0,2        radius of 2
        1,1 1,2 1,3
    2,0 2,1 2,2 2,3 2,4
        3,1 3,2 3,3
            4,2
    I really don't know how to describe the next step. It seemed to me that taking the absolute value of the difference of both the row and the radius and the column and the radius might help. So, I wrote those down:
    Code:
            2,0
        1,1 1,0 1,1
    0,2 0,1 0,0 0,1 0,2
        1,1 1,0 1,1
            2,0
    I then noticed a pattern. The sum of those differences were never greater than the radius. I checked the points outside my diamond to make sure I was on the right track:
    Code:
    4 3 2 3 4
    3 2 1 2 3
    2 1 0 1 2
    3 2 1 2 3
    4 3 2 3 4
    Then I coded it up and tested it for a few other cases. Looks like it works to me.
    Code:
    static void PrintDiamond(int radius)
    {
    	Debug.Assert(radius >= 0);
    
    	int diameter = radius * 2 + 1;
    	for (int line = 0; line < diameter; line++)
    	{
    		for (int col = 0; col < diameter; col++)
    		{
    			if (Math.Abs(col - radius) + Math.Abs(line - radius) <= radius)
    				Console.Write("*");
    			else
    				Console.Write(" ");
    		}
    		Console.WriteLine();
    	}
    }
    I can't really explain how to come up with an algorithm like that. It's just about finding the patterns.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  3. #3
    budding software engineer luigi40's Avatar
    Join Date
    Jun 2004
    Location
    South Coast UK
    Posts
    61
    EXCELLENT POST (excuse my shouting, i thought in this case it was appropriate)

    thanks pianorain

  4. #4
    Registered User CompiledMonkey's Avatar
    Join Date
    Feb 2002
    Location
    Richmond, VA
    Posts
    438
    Quote Originally Posted by pianorain
    I can't really explain how to come up with an algorithm like that. It's just about finding the patterns.
    I agree with this statement. Designing algorithms is a very personal thing that comes from your experience.

    I would suggest that if you struggle with coming up with ways to solve problems, just practice practice practice!

  5. #5
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by CompiledMonkey
    I agree with this statement. Designing algorithms is a very personal thing that comes from your experience.

    I would suggest that if you struggle with coming up with ways to solve problems, just practice practice practice!
    Aye, and most of that practice should be away from the compiler. Implementing an algorithm is trivial compared to designing an algorithm. In the above example, I spent around 20 minutes playing with the numbers, looking for patterns. It took less than 2 minutes to code.

    In my opinion, that's where most programmers fail. They code before they design. If you plan it all out in detail, then coding becomes far easier. I prefer using some sort of spreadsheet (like Excel) and a notepad. No, not Notepad, but a real paper-and-pen notepad with several colors of pens. You can't beat paper for the ease of associating ideas, and Excel is nice for mass number-crunching. Assigning each idea or concept a color of ink keeps all the numbers straight, making it easier to absorb.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  6. #6
    Registered User CompiledMonkey's Avatar
    Join Date
    Feb 2002
    Location
    Richmond, VA
    Posts
    438
    Quote Originally Posted by pianorain
    Aye, and most of that practice should be away from the compiler. Implementing an algorithm is trivial compared to designing an algorithm.
    Correct again. So many people hear a problem and jump to the IDE. Sit down, bust out a pencil and some paper, and think through it visually. It's funny, but every interview I've had with Google and Microsoft has been away from a computer, and hopefully everyone can now see why.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Replies: 5
    Last Post: 04-26-2007, 08:50 AM
  3. page replacement algorithms?
    By Extrovert in forum C++ Programming
    Replies: 1
    Last Post: 08-19-2005, 12:53 AM
  4. relative strength of encryption algorithms (blowfish, des, rinjdael...)
    By duck-billed platypus in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 12-30-2001, 03:20 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21