Threaded Mode | Linear Mode

***l3g1sl4tor*** · 07-14-2010, 06:04 AM

On other forum I found .bat game, guessing of numbers

Code:

@echo off

color 0e

title Joe's Guessing Game!

set /a guessnum=0

set /a answer=%RANDOM%

set variable1=surf33

echo ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

echo Welcome to the Guessing game!

echo.

echo Try and Guess my Number (Made By Chick-Joe!)

echo ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

echo.

:top

echo.

set /p guess=

echo.

if %guess% GTR %answer% ECHO Lower!

if %guess% LSS %answer% ECHO Higher!

if %guess%==%answer% GOTO EQUAL

set /a guessnum=%guessnum% +1

if %guess%==%variable1% ECHO Found the backdoor hey?, the answer is: %answer%

goto top

:equal

echo *************************************************

echo Congratulations,you guessed The Number!

echo.

echo it took you %guessnum% times to get the number!

echo ************************************************

echo MADE BY CHICK-JOE

pause

The winner is the person who is less mistaken... The most effective way to solve this game is using binary tree algorithm Smile

***Back_track*** · 07-14-2010, 07:07 AM

eww batch games Tongue

this would be much better in C Tongue

But could you explain the binary tree algorithm? Perhaps in Pascal Smile

***drdebcol*** · 07-14-2010, 08:44 PM

Basically this is a simple game. You can see the source. You just need to make a loop using goto and that's it.
And about "binary trees", well you need to know pointers very good and than you can
start learning binary trees.
In C you need to learn pointers on structures and structures that have pointers, and than
you can pass on "binary trees" !!

***l3g1sl4tor*** · (This post was last modified: 07-15-2010 12:29 AM by l3g1sl4tor.)

It is not so hard Smile

Imagine that we have 1 array of 100 numbers and we need to find one random which is etc. generated with something as rand() function in php... How that will be done with binary tree search method?

Look at the picture.

[Image: 69335_binarytree.png]

Lets say that circles that are drawn are the data with which we are operating. On first input we have, as I say just one array of 100 numbers (excluding random number which program will generate on the very beginning of program).
In this kind of searching program will divide existing data on half, n times, until it got the solution. So in this our case array 1 (see picture up) will be parted on half on double smaller arrays 2 and 3, then if searched value is not found, arrays 2 and 3 (two halves of array 1) will be parted each on 2 smaller arrays (2 on 4,5 and 3 on 6,7) which will be quarter of our very first array of 100 numbers. This operation will be repeated until random number is found.

What this have with binary so it is called binary tree?
This was my very first question when I first time heard this upper mentioned story Tongue

Lets back to our arrays... you see how number of little (parted) arrays is increasing? first we had 1 then 2, then 4, then we would have 8 in next step. You will notice that all that numbers, (starting from two Tongue

) are extents of number 2. 2=2^1, 4=2^2, 8=2^3, 16=2^4 ... So you see, binary tree in fact is connected with binary system and method! Smile

Methods implementing in Pascal:

First we need to make appropriate type for using binary trees. This type can be made using pointers :

Code:

type

  Element = record

              Key: KeyType;

              { and presumably other fields }

            end;

  BinarySearchTree = ^Component;

  Component = record

                Datum: Element;

                Left, Right: BinarySearchTree

              end;

NOTE : Empty binary tree is marked with nil pointer.

Making empty binary search tree, in which we will later on, insert data :

Code:

function MakeEmptyBinarySearchTree: BinarySearchTree;

begin

  MakeEmptyBinarySearchTree := nil

end;

Inserting data in a search tree :

Code:

procedure InsertIntoBinarySearchTree (Elm: Element; var B: BinarySearchTree);

begin

  if EmptyBinarySearchTree (B) then

    B := MakeSingletonBinarySearchTree (Elm)

  else if Elm.Key < B^.Datum.Key then

    InsertIntoBinarySearchTree (Elm, B^.Left)

  else

    InsertIntoBinarySearchTree (Elm, B^.Right)

end;

Searching binary tree:

Code:

function SearchBinarySearchTree (Sought: KeyType; B: BinarySearchTree;

   var Found: Element): Boolean;

begin

  if EmptyBinarySearchTree (B) then

    SearchBinarySearchTree := False

  else if Sought < B^.Datum.Key then

    SearchBinarySearchTree := SearchBinarySearchTree (Sought, B^.Left, Found)

  else if B^.Datum.Key < Sought then

    SearchBinarySearchTree := SearchBinarySearchTree (Sought, B^.Right, Found)

  else begin

    SearchBinarySearchTree := True; { because Sought = B^.Datum.Key }

    Found := B^.Datum

  end

end;

Write data of binary tree:

Code:

procedure PrintBinarySearchTreeData (B: BinarySearchTree);

begin

  if not EmptyBinarySearchTree (B) then begin

    PrintBinarySearchTreeData (B^.Left);

    writeln (B^.Datum.Key);

    PrintBinarySearchTreeData (B^.Right)

  end

end;

That's only some basic operations with binary trees, for whole story of interacting with it (in pascal), you can visit this link from where I also learned about pointers and binary trees for my past competitions (which was unsuccessful btw Tongue

). Enjoy in searching with this method! Tongue

***drdebcol*** · 07-15-2010, 12:23 AM

I must say that you gave a very good explanation Legislator !!!
Binary tree is a very important part when we talk about graph theory in programming. Binary tree is just the beginning and we have ternary tree, and n-ary tree.
They are used in many algorithms, such as sorting, searching etc.
People avoid trees because of two issues :
-Pointers
-Recursions
You need to know pointers and recursions and to understand basics of graph theory mathematically in order to understand trees and how they work.
Also knowledge about Data Structures always goes with algorithms, another fact is a programming language.

tommy · 10-04-2010, 09:31 PM

nice mathematics techniques are share in this post

***drdebcol*** · 10-05-2010, 03:42 AM

(10-04-2010 09:31 PM)tommy Wrote: nice mathematics techniques are share in this post

Yeah it has elements of Discrete mathematics !