CODEWITHSUNDEEP
algorithmprogramming-languagespseudocode
Hon lo
Hon lo

Reputation: 31

Identifying the programming language the following code is written in

I just started learning computer programming and I want to learn more about programming algorithm. I have bought some reference books. However, when I read the book, I found some codes like this:

function Get-Number(n)
    Q ← NIL
    Enqueue(Q,1)
    While n > 0 do
        x ← Dequeue(Q)
        Unique-Enqueue(Q,2x)
        Unique-Enqueue(Q,3x)
        Unique-Enqueue(Q,5x)
        n ← n – 1
    return x

function Unique-Enqueue(Q,x)
    i ← 0
    while i < |Q| ^ Q[i] < x do
        i ← i + 1
    if i < |Q| ^ x = Q[i] then
        return
    Insert(Q,i,x)

I have learnt some basics of C language but I did not see that kind of code and I cannot understand the algorithm. Do anyone know what kind of programming language is for the above codes? Thank you so much!

Upvotes: 0

Views: 240

Answers (2)

kaushal agrawal
kaushal agrawal

Reputation: 380

Short answer

Calling Get-number(n) returns nth smallest natural number that has only 2, 3, or 5 as prime factors. The list of such numbers looks like this:

{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ...}

Detailed Explanation

The complete code has two functions. I'll explain each step one-by-one.

Get-number(n)

function Get-Number(n)
    Q ← NIL
    Enqueue(Q,1)
    While n > 0 do
        x ← Dequeue(Q)
        Unique-Enqueue(Q,2x)
        Unique-Enqueue(Q,3x)
        Unique-Enqueue(Q,5x)
        n ← n – 1
    return x
  • An empty queue named Q is created. In the next step, we push 1 to it, making Q = [1].
  • We take out the rightmost number x. Then call Unique-Enqueue(Q,2x), Unique-Enqueue(Q,3x), and Unique-Enqueue(Q,5x) respectively.
  • At the end, we return the final value of x. So effectively, we discard the queue Q at the end of the function and retain the final value of x only.

Overall, given an input n, this function will return an output x which can be obtained after doing all the function calls as mentioned above. Now let's look at the other function.

Unique-Enqueue(Q,x)

function Unique-Enqueue(Q,x)
    i ← 0
    while i < |Q| ^ Q[i] < x do
        i ← i + 1
    if i < |Q| ^ x = Q[i] then
        return
    Insert(Q,i,x)
  • In the current Q, keep moving to the right until you hit a number not satisfyingQ[i] < x i.e., find the first number in the queue moving from left to right which is at least as big as x.
  • There are three possible scenarios. If this number is equal to x, stop. If this number is greater than x, insert x before this number. If there is no such number, insert xat the end.

Sample case

Let's say we call Get-number(4):

  • Initially Q = [1].
  • Q = [2,3,5] after first loop.
  • Q = [3,4,5,6,10] after second loop.
  • Q = [4,5,6,9,10,15] after third loop.
  • Q = [5,6,8,9,10,12,15,20] after fourth loop.

Hence Get-number(4) returns 4 since that was the last value for our x.

Upvotes: 1

Robin Green
Robin Green

Reputation: 33063

I'm guessing this is pseudocode. It looks like the meaning of the syntax is as follows:

  • function F(x) declares a new function F with some argument(s)
  • Q <- value assigns value to the variable called Q, creating Q if it does not already exist
  • someFunction(x) calls someFunction, passing in the argument x
  • while is a while loop
  • if...then is an if statement, the same as in C but with a more English-like syntax
  • return x exits the current function and returns x as its return value, or no return value if no return value is specified (void function in C terminology)
  • |Q| yields the size of the collection Q
  • < means the same as in C and in mathematics (less than operator)
  • Q[i] yields the element in collection Q at position i
  • ^ probably means logical AND, because that is what it means in mathematics

Upvotes: 1

Related Questions