Description
Problem Defintion
π is the irrational mathematical constant obtained by dividing a circle’s circumference by its diameter.
Initially, mathematicians expected that, after some point, the digits repeated their previous values, thus
they could writte π as a repeating decimal number. Perhaps, that is the reason why so many decimal parts
of π is calculated. But, that did not happen. Finally, in 1761, mathematician Lambert proved that was
irrational. In other words, the circumference of the circle and its diameter had no common measure in
rational number. The World’s Pi number record was broken by Google employee Emma Haruka Iwao, who
managed to calculate the 31.4 trillion digits of the number.
Figure 1: First 25 decimal number of Pi
In this homework, you should write an app that counts how many times you encounter a 2 digits number
(let’s call it as token) in decimal part of pi. Also, the most common three tokens should be found. A file that
contains approximate pi number is shared with you. For example; how many times some of 2 digit numbers
repeat in first 100 number of pi’s decimal part are given below.
’65’ repeats 1 times
’53’ repeats 2 times
’35’ repeats 1 times
’58’ repeats 2 times
’89’ repeats 2 times
’97’ repeats 3 times
in 3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899
8628034825 3421170679
Page 1 of 4
BLG 223E Data Structures Homework #4
Implementation
1. The necessary libraries and structs for the solution have been given you and explained below. Please
pay attention ’do not change this file’ warning in code files. You have to change counter.cpp file
and if you need you can add some stuff in counter.h file. Also, in token.h, you have to define the value
of TOKEN LENGTH. You are not allowed to include any Standard Template Library (STL) container.
2. Use the below data structure Token that is described in token.h file. The struct contains a char array
token that stores the 2 digit number and an integer value count that stores the count of repeating in
decimal part of π.
struct Token {
char token [ TOKEN_LENGTH ];
int count =0;
};
3. The header file of the source code that you will implement is given below. You can add new functions
or variables if you need, but you are not allowed to drop any of these functions or variables that are
declared in the given header files. You have an array token array in Token type. This array stores
the tokens that you encounenter in decimal part of pi.
# define ARRAY_SIZE 100
# include ” token .h”
struct Counter {
Token token_array [ ARRAY_SIZE ];
int token_count =0;
bool contains ( char * , char );
int findindex ( Token [] , char []);
Token * get_most_common_three ();
void read_and_count ();
};
4. Implement bool contains(char *,char);:
This function checks whether the char array (the first argument) contains the char (the second argument) or not. If it contains, the function returns true, otherwise; false.
5. Implement: int findindex(Token [],char[]):
This function returns the index of desired char array (the second argument) in Token array (the first
argument). If there is no matching, it returns -1.
6. Implement void read and count():
This function reads file that is named as ’pi approximate’, that includes approximate pi number,
and assign each encountered two digits tokens to token array with its count. Note that, tokens
have to consist of two digits and token array have to contains tokens in only decimal part
of pi. For example; ’3.’ is ’.1’ are not accepted forms.
7. Implement: Token *get most common three():
This function returns a pointer of an Token array that includes the most common three tokens.
Main Program, Compilation and Screen Output
A main program is given in main.cpp file. In this way, you can use it to test your implementations.
PLEASE DO NOT CHANGE THIS FILE, OTHERWISE YOUR CODE WILL NOT BE
EVALUATED AND WILL BE GRADED AS 0.
Page 2 of 4
BLG 223E Data Structures Homework #4
To develop your implementation, you can use any IDE (Integrated Developmet Environment) such
as Visual Studio etc. But before submitting, your program should be compiled and ran on Linux
environment using g++ (version 4.8.5 or later). You can test your program on ITU’s Linux Server
using SSH protocol. To compile the code, use the following command:
g++ -std=c++11 -Wall -Werror counter.cpp main.cpp -o hw1
Main program prints out the following messages for a given approximate pi:
COUNTER APPLICATION OF PI ’S DECIMAL
Choose an operation
D: Display
M: Print Most Common Three
E: Exit
Enter a choice {D,M,E}: D
Please enter the token that you want to see how many times it is
encountered in decimal part in pi number ( press ’*’for full list ):
Token : 05
05 1
COUNTER APPLICATION OF PI ’S DECIMAL
Choose an operation
D : Display
M : Print Most Common Three
E : Exit
Enter a choice {D ,M , E }: M
The most common three tokens ;
62 4
97 3
79 3
Your program will be checked by using Calico(https://bitbucket.org/uyar/calico) automatic
checker. Therefore, make sure you not to change main.cpp file You get zero marks if the
automatic checker fails.
Submission Rules
If explanations for this homework is not clear, you can ask your question under the thread that is
specially started for homework 1 (About HW1) on the message board for BLG 223E on NINOVA.
Please check before writing your question whether your question is asked by someone else.
Do not share any code or text that can be submitted as a part of an assignment (discussing ideas
is okay).
.
Make sure you write your name and number in all of the files of your project, in the following format:
/* @Author
Student Name:
Student ID :
Date: */
Only electronic submissions through Ninova will be accepted no later than deadline.
Page 3 of 4
BLG 223E Data Structures Homework #4
You may discuss the problems at an abstract level with your classmates, but you should not share
or copy code from your classmates or from the Internet. You should submit your own, individual
homework.
Academic dishonesty, including cheating, plagiarism, and direct copying, is unacceptable.
Use comments wherever necessary in your code to explain what you did.
Note that YOUR CODES WILL BE CHECKED WITH THE PLAGIARISM TOOLS!
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Page 4 of 4 End of homework.
