Problem Solving with C++ Note: Variables and Arrays

2024-07-16 2024-07-16 2894 字 6 分钟

cpp

Introduction

Arrays
- A collection of variables of the same type.
- An array variable is of an array type, a non-basic data type
There are many non-basic data types:
- Arrays
- Pointers.
- Self-defined types.
- …

Basic data types

In C++, each variable must be have its data type
- It tells the system how to allocate memory spaces and how to interpret those 0s and 1s stored there.
- It will also determine how operations are performed on the variable.
Basic (or build-iun or primitive) data types.
Let’s distinguish literals from variables.
- Literals: items whose contents are fixed, e.g., 3, 8.5, and “Hello world”.
- Variables: items whose values may change.

`int`

int means an integer
- An integer uses 4 bytes to store from $-2^{31}$ to $2^{31} - 1$.
- unsigned (4 bytes): from 0 to $2^{32} - 1$
- short (2 bytes): -32768 to 32767
- long: the same as int. \a
- The C++ standard only requires a compiler to ensure that:
  - The space for a long variable >= the space for an int one.
  - The space for an int variable >= the space for a short one.
- short and long just create integers with different “lengths”
  - In most information systems this is not an issue.
The limits of C++ basic data types are stored in <climits>,
- see reference: https://cplusplus.com/reference/climits/.

#include <iostream>
#include <climits>

int main()
{
    using namespace std;

    cout << INT_MIN << " " << INT_MAX << endl;
    
    return 0;
}

We may use the sizeof operator to know the size of a variable or a type.

#include <iostream>
#include <climits>

int main()
{
    using namespace std;
    
    cout << "int " << sizeof(int) << " bytes" << endl;
    cout << "short " << sizeof(short) << " bytes" << endl;
    cout << "long " << sizeof(long) << " bytes" << endl;
    cout << "long long " << sizeof(long long) << " bytes" << endl;
    cout << "char " << sizeof(char) << " bytes" << endl;
    cout << "float " << sizeof(float) << " bytes" << endl;
    cout << "double " << sizeof(double) << " bytes" << endl;
    cout << "long double " << sizeof(long double) << " bytes" << endl;
    cout << "unsigned int " << sizeof(unsigned int) << " bytes" << endl;
    cout << "unsigned short " << sizeof(unsigned short) << " bytes" << endl;
    cout << "unsigned long " << sizeof(unsigned long) << " bytes" << endl;
    cout << "unsigned long long " << sizeof(unsigned long long) << " bytes" << endl;
    cout << "unsigned char " << sizeof(unsigned char) << " bytes" << endl;
    cout << "INT_MAX " << INT_MAX << endl;
    cout << "INT_MIN " << INT_MIN << endl;
    cout << "UINT_MAX " << UINT_MAX << endl;
    cout << "SHRT_MAX " << SHRT_MAX << endl;
    cout << "SHRT_MIN " << SHRT_MIN << endl;
    cout << "USHRT_MAX " << USHRT_MAX << endl;
    cout << "LONG_MAX " << LONG_MAX << endl;
    cout << "LONG_MIN " << LONG_MIN << endl;
    cout << "ULONG_MAX " << ULONG_MAX << endl;
    cout << "LLONG_MAX " << LLONG_MAX << endl;
    cout << "LLONG_MIN " << LLONG_MIN << endl;
    cout << "ULLONG_MAX " << ULLONG_MAX << endl;
    return 0;
}

int 4 bytes
short 2 bytes
long 4 bytes
long long 8 bytes
char 1 bytes
float 4 bytes
double 8 bytes
long double 8 bytes
unsigned int 4 bytes
unsigned short 2 bytes
unsigned long 4 bytes
unsigned long long 8 bytes
unsigned char 1 bytes
INT_MAX 2147483647
INT_MIN -2147483648
UINT_MAX 4294967295
SHRT_MAX 32767
SHRT_MIN -32768
USHRT_MAX 65535
LONG_MAX 2147483647
LONG_MIN -2147483648
ULONG_MAX 4294967295
LLONG_MAX 9223372036854775807
LLONG_MIN -9223372036854775808
ULLONG_MAX 18446744073709551615

Be aware of overflow

#include <iostream>
#include <climits>

int main()
{
    using namespace std;
    
    int i = 0;
    short sGood = 32765;

    while (i < 10)
    {
        short sBad = sGood + i;
        cout << "sBad: " << sBad << endl;
        i += 1;
        
    }

    return 0;
    
}

sBad: 32765
sBad: 32766
sBad: 32767
sBad: -32768
sBad: -32767
sBad: -32766
sBad: -32765
sBad: -32764
sBad: -32763
sBad: -32762

`char`

char means a character
- Use one byte (-128 to 127) to store English letters, numbers, symbols, and special characters (e.g., the newline character).
- Cannot store, e.g., Chinese characters.
It is also an integer.
- These characters are encoded with the ASCII code in most PCs
- ASCII = American Standard Code for Information interchange.
Nevertheless, avoid doing arithmetic on char.

#include <iostream>

int main()
{
    using namespace std;
    
    for (int c = 33; c <= 126; c++)
    {
        cout << c << " " << static_cast<char>(c) << endl;
    }

    return 0;
    
}

– Revised version

#include <iostream>

int main()
{
    using namespace std;

    cout << "   0 1 2 3 4 5 6 7 8 9" << endl;
    cout << " 3      ";
    
    for (int c = 33; c <= 126; c++)
    {
        if (c % 10 == 0)
        {
            if (c / 10 <= 9)
                cout << " " << c / 10;
            else
                cout << c / 10;
        }

        char cAsChar = static_cast<char>(c);
        cout << " " << cAsChar;
        
        if (c % 10 == 9)
            cout << endl;
    }

    return 0;
}

`bool`

A bool variable uses 1 byte to record one Boolean
All non-zero values are treated as true.

`float` and `double`

float and double are used to declare fractional numbers.

#include <iostream>
#include <cmath>

int main()
{
    using namespace std;

    for (int i = 0; i < 20; i++)
    {
        float f = sqrt(i);
        cout.setf(ios::fixed);
        cout.setf(ios::showpoint);
        cout.precision(2);
        cout << f << "  " << i << endl;   
    }

    return 0;
    
}

Precision can be a big issue
- As modern computers store values in bits, most decimal fractional numbers can only be approximated.

#include <iostream>
#include <cmath>

int main()
{
    using namespace std;

    int bad = 0;

    for (int i = 0; i < 20; i++)
    {
        float f = sqrt(i);
        cout.setf(ios::fixed); // 设置浮点数的输出格式为定点表示法。默认情况下，浮点数的输出可能会采用科学计数法（如 1.23e+02），而 std::fixed 则强制使用常规的十进制格式。
        cout.setf(ios::showpoint); // 操纵符确保输出浮点数时始终显示小数点，即使小数部分为零。
        cout.precision(2);
        cout << f << "  " << i << "  ";

        if(f * f != i)
        {
            cout << "Error: " << f << " * " << f << " != " << i << endl;
            bad++;
        }

        cout << endl;
    }

    cout << "There are " << bad << " bad values." << endl;

    return 0;
    
}

#include <iostream>
#include <cmath>
#include <iomanip>
// for using 'setprecision' manipulator \a. 
// 通常与其他操纵符一起使用，如 std::fixed 和 std::showpoint. 
// 'setprecision' 只影响其后的单个输出操作，不会持续影响后续的输出。

int main()
{
    using namespace std;

    for (int i = 0; i < 100; i++)
    {
        float f = sqrt(i);

        cout << f << " "<< fixed << showpoint << setprecision(10) << f * f << " " << endl;
    }

    return 0;
    
}

Remedy: “imprecise” comparisons

if (abs(f * f - i) > 0.0001)
{
    cout << "!!!!";
    bad++
}

The error tolerance can be neither too large nor too small.
- It should be set according to the property of your own problem.
To learn more about this issue. study Numerical Methods, Numerical Analysis, Scientific Computing.

Constants

In a program doing calculations regarding circles, the value of $\pi$ may be used repeatedly.
We do not want to write many 3.14 throughout the program!
We may declare a named constant MY_PI using const double MY_PI = 3.14 once and then use MY_PI repeatedly.
In this case, this variable is actually a symbolic constant.
- We want to prevent it from being modified, using const modifier.
- It is suggested to use capital character and underlines to name constants, e.g., MY_PI.

Casting

Variables are containers
Variables of different types are containers of different sizes/shapes.
A big container may store a small item. A big item must be “cut” to be stored in a small container.
Changing the type of a variable or literal is called casting
There are two kinds of casting:
- Implicit casting: from a small type to a large type.
- Explicit casting: from a large type to a small type.
When implicit casting occurs, there is no value of precision loss.
- The system does that automatically.
- The value of that variable or literal does not change.
- There is no need for a programmer to indicate how to implicitly cast one small type to a large type.
To cast a large type to a small type, a programmer is responsible for indicating hwo to do it explicitly.
Suppose we want to store 5.6 to an integer:
- int a = 5.6; is not good.
- int a = static_cast<int>(5.6); it better.
- In general form: static_cast<type>(expression)
There are four different explicit casting operators:
- static_cast, dynamic_cast, reinterpret_cast, and const_cast.
- For basic data types, static_cast is enough.
- static_cast: Used for explicit conversions between related types, executed at compile time.
- dynamic_cast: Used for safe downcasting in class hierarchies, checked at runtime.
- const_cast: Used to remove the const or volatile attribute from an object.
- reinterpret_cast: Used for low-level reinterpretation of bit patterns, generally unsafe and should be used with caution.
Casting can be a big issue when we work with non-basic data types.
Casting a character to an integer.

#include <iostream>

int main()
{
    using namespace std;

    char c = 254;
    int a = 10;

    cout << c + a << endl; // result: 264?, Real result: 8; 
                           // Explanation: c is a char, so it is converted to an int, which is -2. -2 + 10 = 8.

    return 0;
    
}

Avoid doing arithmetic operation on char.

1-D arrays

Suppose we want to write a program to store five student’s scores.
We may declare 5 variables.
- int score1, score2, score3, score4, score5;
What if we have 500 students? How to declare 500 variable?
Even if we have only 5, we are unable to write a loop to process them.

for (int i = 0; i < 5; i++)
{
    cout << score1<< endl; // and then?
}

An array is a collection of variables with the same type.
To declare five integer variables for scores, we my write: int score[5];.
- These variables are declared with the same array name (score)
- They are distinguished by their inices: cin >> score[2].
Arrays are often used with loops.
- Quite often the loop connter is used as the array index.

int score[5];
for (int i = 0; i < 5; i++)
{
    cin >> score[i];
}

An array is also a (non-basic) type.
- The type of score is an int.
- What is this: cout << score:

#include <iostream>

int main()
{
    using namespace std;

    int score[5];
    for (int i = 0; i < 5; i++)
    {
        cin >> score[i];
    }

    cout << score << endl; // result: 00000073768FFDB0 \a

    for (int i = 0; i < 5; i++)
    {
        cout << score[i] << " "; 
    }
    cout << endl;    

    return 0;
    
}

Array initialization
- Arrays are not initialized automatically.
- Various ways of initializing an array:

int daytsInMonth1[12] = {31, 28, 31, 30, 31, 30, 31, 31, 31, 30, 31, 30, 31};
int daytsInMonth2[] = {31, 28, 31, 30, 31, 30, 31, 31, 31, 30, 31, 30, 31};
int daytsInMonth3[12] = {31, 28, 31}; // Nine 0s

int daytsInMonth4[3] = {31, 28, 31, 2}; // error.

To initialize all elements to 0: int dayInMonth[12] = {0};
An example: inner product

// This program is used to calculates the inner product of two vectors (4-dimensional).
#include <iostream>

int main()
{
    using namespace std;

    int a[4] = {1, 2, 3, 4};
    int b[4] = {5, 6, 7, 8};

    int result = 0;

    for (int i = 0; i < 4; i++)
    {
        result += a[i] * b[i];
    }
    
    cout << result << endl; // result: 70
    return 0;
    
}

Modify the above program to allow a user to decide the values of the two vectors.

// This program is used to calculate the inner product of two vectors.
// The dimension of the vectors is decided by the user.
// Here we use pointer and dynamic array.
#include <iostream>

int main()
{
    using namespace std;

    int n;
    cout << "Enter the dimension of the vectors: ";
    cin >> n;

    int *a = new int[n];
    int *b = new int[n];

    cout << "Enter the elements of the first vector:" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    cout << "Enter the elements of the second vector:" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }

    int result = 0;

    for (int i = 0; i < n; i++)
    {
        result += a[i] * b[i];
    }

    cout << "The inner product of the two vectors is: " << result << endl;

    // Free the allocated memory
    delete[] a;
    delete[] b;

    return 0;
}

Write a program that calculate the sum of two vectors.

// This program is used to calculate the sum of two vectors. (4-dimensional).
#include <iostream>

int main()
{
  using namespace std;

  int a[4] = {1, 2, 3, 4};
  int b[4] = {5, 6, 7, 8};
  int result[4] = {0};

  for (int i = 0; i < 4; i++)
  {
      result[i] = a[i] * b[i];
  }

  cout << "Result: [";
  for (int i = 0; i < 3; i++ )
  {
      cout << result[i] << ", ";
  }
  cout << result[3];
  cout << "]" << endl;

  return 0; 
}

In C++, it is allowed for one to “go outside an array” -> No compilation error! \a
May or may not generate a run time error: If our program try to access a memory space allocated to another program, the operating system will terminate our program.
The result is unpredictable.
A programmer must be aware of array bounds by herself/himself.
Memory allocation for arrays
- When we declare an array: int score[5];

The system allocates memory spaces according to the type and length.
The array variable indicates that beginning address of the space.
When we access an array element:
- The array index indicates the amount of offset for accessing a memory space.
- score[i] means to take the variable stored at “starting from score[0], offset by i units.
- So score[i] is always accepted by the compiler for any value of i. So, always be carefurl using array.
Finding the array length
- One way of finding the array length is to use sizeof, it returns the total number of bytes allocated to that array.

int array[] = {1, 3, 4};
int length = sizeof(array) / sizeof(array[0]); // do not use `sizeof(a) / sizeof(int)`
for (int i = 0; i < length; i++)
{
    cout << array[i] << endl;
}

Things you cannot (should not) do:
- Suppose that you have two arrays a1 and a2:
  - Even if they have the same length and their elements have the same type, you cannot write a1 = a2. This results in a syntax error.
  - You also cannot compare two arrays with ==, >, <, etc.
  - a1 and a2 are just two memory address.
  - To copy one array to another array, use a loop to copy each element one by one.
- You should not declare an array whose length is non-constant
  - This creates a syntax error in some compiler.
  - In ANSI C++, the length of an array must be fixed when it is declared.

// DO NOT DO THIS
int x = 0;
cin >> x;
// VERY BAD!
int array[x];
array[2] = 3;

- The index of an array variable should be integer.

// Do this
int x = 0;
cin >> x;
// good
int* array = new int[x]; // Dynamic unnamed array
array[2] = 3;

Multi-D arrays

While a one-dimensional array is like a vector, a two-dimensional array is like a matrix or table.
Intuitively, a two-dimensional array is composed by rows and columns.
- To declare a two-dimensional array, we should specify the numbers fo rows and clumns: data_type array_name[rows][columns].
We may initialize a two-dimensional array as follows:

int score[2][3] = {{3, 4, 5}, {7, 8, 9}};
int score[][3] = {4, 5, 6, 7, 8, 9}; // row number can be omitted

int score[2][3] = {{4, 5}, {7, 8, 9}};
cout << score[0][2]; // 0

int score[2][3] = [4, 5, 7, 8, 9];
cout << score[0][2]; // 7

Example: tic-tac-toe
Two-dimensional arrays are not actually rows and columns.
A two-dimensional array is actually several one-dimensional arrays.
int a[2][3]:
a[0][0] is the first element.
a[0][1] is the second element.
a[1][0] is the fourth element.
Two dimensional arrays are stored linealy.
And still consecutively.

#include <iostream>

int main()
{
    using namespace std;

    int a[2][3] = {{2, 1, 3}, {5, 6, 7}};
 
    cout << a << " " << a[0] << endl; // result: 0x7ffebf1b3b40 0x7ffebf1b3b40
    cout << a[1] << " " << a + 1 << endl; // result: 0x7ffebf1b3b4c 0x7ffebf1b3b4c
    cout << sizeof(a) << " " << sizeof(a[0]) << " " << sizeof(a[1]) << endl; // result: 24 12 12

    return 0;
}

Problem Solving with C++ Note: Variables and Arrays

Introduction

Basic data types

int

char

bool

float and double

Constants

Casting

1-D arrays

Multi-D arrays

`int`

`char`

`bool`

`float` and `double`