ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.03.2024
Просмотров: 12
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
-
Примеры определения и реализации АТД
Пример 1. Реализация АТД с применением типа struct для объединения данных в единую структуру.
-
Условие задачи
В заданном множестве из n натуральных чисел найти все числа Армстронга. Число Армстронга — это натуральное число, которое равно сумме цифр числа, возведенных в степень равную количеству цифр в числе. Пример, 153=13+53+33.
-
Постановка задачи.
Дано. Множество из n натуральных чисел
Результат. Сформировать массив из тех чисел исходного множества, которые являются числами Армстронга (153=13+53+33).
-
АТД задачи
АТД setNumbersArmstrong
{
Данные
n – размер входных данных (или размер задачи)
Х – множество из n натуральных чисел
typeX – тип множества
typeitem – тип элемента множества Х
Операции
-
Заполнение исходного массива значениями с клавиатуры
Предусловие. n – число заполняемых элементов,0 ≤n
Постусловие. Заполненный массив X из n элементов. Нет возвращаемого значения.
input_X(typeX Х, unsigned int n);
-
Вывод значений массива X
Предусловие. n>0, X – выводимый массив
Постусловие. Вывод значений массива. Нет возвращаемого значения.
output_X(typeX Х, unsigned int n);
-
Функции декомпозиции (подзадачи исходной задачи, которые использует основной алгоритм)
//Определение количества цифр в числе
Предуслвие. x≥10 – исходное число типа typeitem
Постусловие. Результат целое, количество цифр вчисле х
count(typeitem);
//Возведение целого числа в степень p
Предуслвие. а>0 – цифра числа типа typeitem, p>0 – степень
Постусловие. Результат целое, возведение а в степень p
pow_1(typeitem a, unsigned int p);
//Определение числа Армстронга
Предуслвие. х>0 входное значение – целое натуральное число
Постусловие. Результат true если х число Армстронга, false иначе
Armstrong(typeitemx);
//Формирование массива чисел Армстронга
Предусловие. Х множество значений размера n>0. Y – множество типа typeX, формируемое функцией
Постусловие. Результат массив Y из n элементов. Если в массиве А нет чисел Армстронга, то n=0 и массив Y пустое множество.
newArrayY(typeX X, typeX Y);
}
-
Набор тестов для тестирования программы
| Номер теста | Исходные данные | Ожидаемый результат |
| 1 | n=3 А(1, 2, 3) | nY=3 Y(1,2,3) |
| 2 | n=5 А(11, 12, 13,14, 15) | nY=0 B() Нет таких чисел |
| 3 | n=3 A(1,22,153) | nY=2 B(1,153) |
-
Реализация АТД и код программы
#include
#include"stdlib.h"
#include"string.h"
using namespace std;
typedef unsigned int typeitem;
const unsigned int N = 100;
//Определение данных АТД задачи
struct typeX{
unsigned int n=0;
typeitem X[N] = {};
typeX(int n1) { n = n1; }
typeX() { n = 0; }
};
//Операции АТД – прототипы функций
//Вывод множества
void output_X(typeX s);
//Заполнение множества с клавиатуры
void input_X(typeX &s);
//Формирование массива Y (множества) из чисел Армстронга исходного множества X
void newArrayY(typeX s, typeX &Y);
//Определение количества цифр в числе x
int count(typeitem x);
//Возведение целого числа в степень p>0
typeitem pow_1(typeitem a, unsigned int p);
//Является ли число х числом Армстронга
bool Armstrong(typeitem x);
//Реализация операций АТД
//Заполнение множества с клавиатуры
//Предусловие. n – число заполняемых элементов, 0 ≤n < N, X – массив с переменной
// верхней границей.
//Постусловие. Заполненный массив X из n элементов.Нет возвращаемого значения.
void input_ar(typeX &s)
{
cout << "Vvedite "<
for (unsigned int i = 0; i < s.n; i++)
cin >> s.X[i];
}
//Вывод множества
//Предусловие.n > 0, X – выводимый массив
//Постусловие.Вывод значений массива.Нет возвращаемого значения.
void output_ar(typeX s)
{
cout << "Массив " << endl;
for (unsigned int i = 0; i < s.n; i++)
cout << "X[" << i << "]=" << s.X[i] << endl;
}
//Формирование массива (множества) из чисел Армстронга исходного множества
//Предусловие. Х множество значений размера n > 0. Y – множество типа typeX,
// формируемое функцией
//Постусловие. Результат массив Y из n элементов.Если в массиве А нет чисел
// Армстронга, то n = 0 и массив Y пустое множество.
void newArrayY(typeX s, typeX &Y) {
Y.n = 0;
for (unsigned int i = 0; i < s.n; i++) {
if (Armstrong(s.X[i]) == true)
{
Y.X[Y.n] = s.X[i];
Y.n++;
}
}
}
//Определение количества цифр в числе
//Предуслвие. x≥10 – исходное число типа typeitem
//Постусловие. Результат целое, количество цифр в числе х
int count(typeitem x) {
int k = 0;
while (x) {
k++;
x = x / 10;
}
return k;
}
//Является ли число х числом Армстронга
//Предусловие. х > 0 входное значение – целое натуральное число
//Постусловие. Результат true если х число Армстронга, false иначе
bool Armstrong(typeitem x) {
int p = count(x); //количество цифр в числе и значение степени
typeitem sum = 0;
typeitem copyx = x; //копия исходного числа
while (x) {
sum += (unsigned int) pow_1(x % 10, p);
x = x / 10;
}
if (copyx == sum)
return true;
else return false;
}
//Возведение целого числа в степень p>0
//Предуслвие.а>0 – цифра числа типа typeitem, p>0 – степень
//Постусловие.Результат целое, возведение а в степень p
typeitem pow_1(typeitem a, int p) {
typeitem R = 1;
if (p == 1) return a;
while (p) {
R *= a;
p--;
}
return R;
}
//Основная программа, тестирующая операции на подготовленных тестах
nt main(int argc, char* argv[])
{ int n;
cout << "Vvedite razmer mnogestva a"; cin >> n;
if (n > 0 && n < N) {
typeX a(n), b;
input_ar(a);
newArrayY(a, b);
if (b.n > 0){
cout << "Numbers Armstronga in array a\n";
output_ar(b);
}
else
cout << "Not Numbers Armstronga in array a\n";
}
else
cout << "n<0 or n>"<
return 0;
}
Пример 2. Реализация АТД без объединения данных в единую структуру
#include
#include"stdlib.h"
#include"string.h"
using namespace std;
const unsigned int N = 100;
//Заполнение множества с клавиатуры
//Предусловие.n – число заполняемых элементов, 0 ≤n < N, X – массив с переменной верхней границей.
//Постусловие.Заполненный массив X из n элементов.Нет возвращаемого значения.
void input_ar(int *s,int n)
{
cout << "Vvedite " <
for (int i = 0; i < n; i++)
cin >> s[i];
}
//Вывод множества
//Предусловие. n > 0, X – выводимый массив
//Постусловие. Вывод значений массива.Нет возвращаемого значения.
void output_ar(int* s, int n)
{
cout << "Массив " << endl;
for (int i = 0; i < n; i++)
cout << "s[" << i << "]=" << s[i] << endl;
}
//Определение количества цифр в числе
//Предуслвие.x≥10 – исходное число типа int
//Постусловие. Результат целое, количество цифр в числе х
int count(int x) {
int k = 0;
while (x) {
k++;
x = x / 10;
}
return k;
}
//Возведение целого числа в степень p>0
//Предуслвие. а>0 – цифра числа типа int, p>0 – степень
//Постусловие. Результат целое, возведение а в степень p
int pow_1(int a, int p) {
int R = 1;
if (p == 1) return a;
while (p) {
R *= a;
p--;
}
return R;
}
//Определение числа Армстронга
//Предусловие. х > 0 входное значение – целое натуральное число
//Постусловие. Результат true если х число Армстронга, false иначе
bool Armstrong (int x) {
int p = count(x); //количество цифр в числе и значение степени
int sum = 0;
int copyx = x; //копия исходного числа
while (x) {
sum += (int)pow_1(x % 10, p);
x = x / 10;
}
if (copyx == sum)
return true;
else return false;
}
//Формирование массива (множества) из чисел Армстронга исходного множества
//Предусловие. Х множество значений размера n > 0. Y – множество типа typeX, формируемое функцией
//Постусловие. Результат массив Y из n элементов.Если в массиве А нет чисел Армстронга, то n = 0 и массив Y пустое множество.
void newArrayY(int* s, int ns, int* Y, int &nY) {
nY = 0;
for (int i = 0; i < ns; i++) {
if (Armstrong(s[i]) == true)
{
Y[nY] = s[i];
nY++;
}
}
}
int main()
{
unsigned int n = 0;
cout << "Vvedite razmer mnogestva a"; cin >> n;
if (n > 0 && n < N) {
int a[N], b[N];
int nb=0;
input_ar(a,n);
newArrayY(a,n, b,nb);
if (nb > 0) {
cout << "Numbers Armstronga in array a\n";
output_ar(b,nb);
}
else
cout << "Not Numbers Armstronga in array a\n";
}
else
cout << "n<0 or n>" << N << "\n";
return 0;
std::cout << "Hello World!\n";
}
-
Контрольные вопросы
-
Дайте определение структуре данных. -
Какие три операции над структурой данных называют базовыми? -
Что определяет тип данных в языках программирования? -
Сколько ячеек памяти связано с именем переменной простого типа? -
Сколько ячеек памяти связано с именем массива размером n? -
Перечислите свойства, характеризующие структуру данных массив. -
Какой тип языка программирования С++ пользуется для представления структуры данных, элементы которой различного типа? -
Могут ли элементом структуры struct быть другие структуры: массив, строка, указатель на другую структуру, другая структура? -
Определите тип данных для представления в программе точки на плоскости (декартова система координат). Определите структуру для хранения данных по n точкам. -
Перечислите свойства структуры, организованной на типе struct. -
Как называется область оперативной памяти, предназначенная для хранения значения простого типа? -
Что определяет размер ячейки оперативной памяти? -
Как можно описать организацию оперативной памяти на логическом уровне? -
Что определяет абсолютный адрес ячейки памяти? -
Какой способ хранения элементов структуры данных реализует одномерный массив? -
Какой способ хранения элементов структуры данных реализуется при определении пользовательского типа struct в C++? -
Что нужно знать (определить), чтобы получить прямой доступ к значению ячейки оперативной памяти? -
Какой способ хранения структур данных позволяет обеспечит прямой доступ к элементам структуры? -
Приведите формулу, по которой определяется адрес i - ого элемента массива х. Какой параметр в формуле представляет смещением и почему его так называют? -
Что представляет собой структура данных, имеющая векторное хранение элементов? Опишите. -
Приведите характеристики статического массива. -
Какие переменные называют локальными? -
Как организована область оперативной памяти для хранения локальных переменных? -
Что определяет понятие «время жизни переменной»? -
Если алгоритм функции вычисляет одно значение простого и ссылочного типа, что нужно включить в код функции? (приведите пример) -
Какую ошибку допустил программист при разработке функции func?
#include
const int n=10;
int *func(){
int a[n]={1,2,3,4,5,6,7,8,9,0};
return a;
}
int main(){
int *b=func();
for(int i=0;i
cout<
}
-
Статическому массиву А выделена память под 100 элементов. В него ввели только десять значений (n=10). Алгоритм функции func1 добавил по индексу 11 еще одно значение. Определите ошибку, которую допустил программист при создании функции func1?
#include
const int m=100;
void func1(int *a,int n,int x){
a[n]=x; n++;
}
int main(){
int n=10;
int a[m]={1,2,3,4,5,6,7,8,9,0};
func1(a,n,20);
for(int i=0;i
cout<
}
-
Как объявить типизированный указатель в программе на языке С++? -
Как объявить указатель без типа в программе на языке С++? -
Какие арифметические операции допустимы над указателем в С++? -
Программист написал неверный код копирования массива, который содержал операторы:
int x[]={1,2,3,4,5}; int *y=x;
Объясните его ошибку.
-
Объясните суть операции «разыменование» для указателя. -
Приведите модель выполнения операции удаления значения массива из заданной позиции с сохранением порядка следования значений после удаленного значения. -
Приведите алгоритм удаления значения массива из заданной позиции, не сохраняя порядок следования значений после удаленного значения. -
Укажите условие, при котором допустима операция вставки нового значения в статический массив. -
Приведите модель выполнения операции вставки нового значения в заданную позицию массива с сохранением порядка следования значений после вставленного значения. -
Опишите различие алгоритмов операций вставки и добавления нового значения в массив.
