Найти наименьшее общее кратное для всех элементов массива минимальное число, которое делится на все элементы массива без остатка
 Скачать 37.93 Kb.
|
|
Задачи Задачи оформляются в виде функций с передачей всех входных и выходных данных через формальные параметры и результат. Задачи, работающие со строками, по заданию преподавателя реализовать либо с использованием массивов char[], либо с использованием указателей char* и операций вида *p++. Для функции привести пример вызова из main со статическими входными параметрами. Найти наименьшее общее кратное для всех элементов массива - минимальное число, которое делится на все элементы массива без остатка. int f( int A []) { constint n = 10; inti, nok = 1, j; for (i = 0; i { j = A[i]; if (j j = nok; for (; j <= nok*A[i]; j++) { if (j%A[i] == 0 &&j%nok == 0) { nok = j; break; } } } returnnok; } 2.Написать функцию проверки, является ли заданное число простым. С ее помощью написать программу поиска простых чисел в диапазоне 1000-2000, две любые части которого - также простые (например, 1997, 1-997,19-97,199-7) bool simple(intx) { int n = 0; for (n = 2; n { if (x%n == 0) break;// перебор всех значени n до первого деления без остатка } if (n == x) returntrue; elsereturnfalse; } int f(intA[]) { int c = 0; for (int i = 1000; i < 2000; i++) { int temp = i,j=1,k=0; bool good = false; if (simple(temp) == true) good = true; else good = false; if (simple(temp / 1000) == true&& simple(temp % 1000)) good = true; else good = false; if (simple(temp / 100) == true&& simple(temp % 100)) good = true; else good = false; if (simple(temp / 10) == true&& simple(temp % 10)) good = true; else good = false; if (good = true) { A[c] = i; c++; } } return c; } 3. Сформировать массив простых чисел в диапазоне от 2 до заданного. Очередное простое число определяется попыткой деления нацело числа на все уже накопленные простые числа. void Mas(int n){ int A[n]; // создается массив для простых чисел int i=1, j,k; // i-счетчик; j-переменная для перебора чисел от 2 до n; k-переменная для подсчета элементов массива bool check; A[i]=2; // по условию сказанно что первым элементом мас. будет 2 k=i; for(j=3; j for(i=1; i if(j%A[i]!=0){ // проверка check=true; } else{ check=false; break; // если j делится хотя бы на один из уже имеющихся простых чисел из массива то цикл сбрасывается } } if(check==true){ // если j прошла проверку то это число вносится в массив A[k+1]=j; k++; } } for(i=1; i<=k; i++){ // вывод массива cout << A[i] << endl; } } 4.Любая целочисленная денежная сумма n>7 может быть выдана без сдачи “трешками” и “пятерками”. Программа находит эти числа для заданного n. void S(int n){ int m3,m5; m3=m5=0; while(n%3!=0 && n%5!=0){ n=n-3; m3++; } if(n%3==0) m3=n/3; if(n%5==0) m5=n/5; cout << "m3=" << m3 << endl << "m5=" << m5 << endl; } 5. На заданном интервале найти все числа, цифры которых находятся в строго возрастающем порядке (например, 532). int func(int a, int b){ int k=0, i, n, x, i2; // k-счетчик искомых чисел; i-переменная для перебора чисел в заданном диапазоне bool check; for(i=a; i x=i; // x-переменная для проведения мат. операций с числом n=1; while(x/10!=0){ x=x/10; n++; // n-считает кол-во цифр в числе } x=i; // возвращаем х исходное значение for(int i2=1; i2 if((x%10)<((x/10)%10)){ // проверяем находятся ли цифры в возраст порядке x=x/10; check=true; } else{ check=false; break; // если число не проходит проверку, цикл проверки завершается и происходит переход к следующему числу } } if(check==true) // если проверка пройдена счетчик чисел увелич. k++; } return k; } 6.Число Армстронга – такое число из k цифр, для которого сумма k-х степеней его цифр равна самому этому числу, например 153=13+53+33. Найти все трехзначные числа Армстронга. void func(){ int i, a, b, c; // a b c это цифры числа for(i=100; i<999; i++){ // i перебирает все трехзначные числа a=i/100; a=a*a*a; b=(i/10)%10; b=b*b*b; c=i%10; c=c*c*c; if((a+b+c)==i) // является ли это число, числом Армстронга cout << a+b+c << endl; // если да, то оно выводится } } 7.Найти все двухзначные (трехзначные) числа, которые совпадают с последними цифрами своих квадратов, например, 252=625, 762=5676. void func(){ int i, x; for(i=10; i<99; i++){ // i перебирает числа x=i*i; // возведение числа в квадрат и присваивание занения переменной х if(x%100==i) // проверка заданного условия cout << x << "---" << i << endl; // вывод квадрата и числа при прохождении условия } // то же самое, только для трехзначных for(i=100; i<999; i++){ x=i*i; if(x%1000==i) cout << x << "---" << i << endl; } } 8.Число называется совершенным, если оно равно сумме всех своих делителей, например, 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные числа в заданном интервале. void func(int a, int b){ int i, i2, x; for(i=a; i i2=1; x=0; while(i2<(i-1)){ // в цикле сумируются делители числа if(i%i2==0) x=x+i2; i2++; } if(x==i) // проверка условия Идеального числа cout << i << endl; // вывод числа } } 9.Найти все числа в заданном диапазоне, которые делятся на любую из своих цифр. int f(inta,intb,intB[]) { int c = 0; for (int i = a; i { int temp = i, n = 0, s = 0; int A[30]; for (int t = temp; t!=0; n++,t/=10); for (int j = 0, ch = temp; j < n; j++) { A[j] = ch % 10; ch /= 10; } for (int j = 0; j < n && s == 0 && A[j]!=0; j++) { if (temp%A[j] == 0) s = 0; else s = 1; } if (s == 0) { B[c] = temp; c++; } } return c; } 10.Найти числа в диапазоне 100-10000, для которых куб суммы цифр равен значению самого числа (например, 512 - 5+1+2=8). void func(){ int i, a, b, c, d; // a b c d это цифры числа for(i=100; i<999; i++){ // i перебирает все трехзначные числа a=i/100; b=(i/10)%10; c=i%10; if(((a+b+c)*(a+b+c)*(a+b+c))==i) // подходит ли число под заданное условие cout << i << endl; // если да, то оно выводится } // то же самое только для тысяч for(i=1000; i<9999; i++){ a=i/1000; b=(i/100)%10; c=(i/10)%10; d=i%10; if(((a+b+c+d)*(a+b+c+d)*(a+b+c+d))==i) cout << i << endl; } } 11.Разложить число на простые множители (например 36=3*3*2*2). Результат – последовательность множителей в массиве, ограниченная 0. int func(int x){ int A[x]; // создаем массив для множителей int i=1; if((x%2!=0)&&(x%3!=0)&&(x%5!=0)&&(x%7!=0)) // проверка, является ли число простым cout << "eror" << endl; while(x%2==0){ // деление числа на каждую простую цифру x=x/2; A[i]=2; i++; } while(x%3==0){ x=x/3; A[i]=3; i++; } while(x%5==0){ x=x/5; A[i]=5; i++; } while(x%7==0){ x=x/7; A[i]=7; i++; } if(x==1){ // если после деления на все цифры число стало равно 1 то циклом выводится массив x=i; for(i=1; i cout << A[i] << endl; } } else{ // если нет, значит осталось простое число которое так же вносится в массив, который выводится циклом A[i]=x; x=i; for(i=1; i<=x; i++){ cout << A[i] << endl; } } } 12.Определить в массиве максимальную длину последовательности расположенных подряд возрастающих значений и возвратить индекс ее начала.ЗАМЕТКА – функция возвращает длину последовательности а переменная по ссылке ее индекс int f(intB[],intn,int&d) { int c = 0, l = 0; int A[256],t = 0; bool up = false; for (inti = 0; i { if (B[i + 1] >B[i]) l++; else { A[i-l] = l+1; l = 0; } } int max = A[0]; for (inti = 0; A[i] != 0;i++) if (A[i] > max) { max = A[i]; d = i; } returnmax; } 13.Подсчитать количество слов в строке. int str(char B[]){ int k=0; int i=1; while(B[i]!=0){ i++; if(B[i]==' ' || B[i]==0) k++; } return k; } 14.Найти в строке слово минимальной длины и возвратить индекс его начала. void str(char B[]){ int k1=0, k2=0; int i=0, l=1; while(B[i]!=0){ if(B[i]==' '){ if(k1 k2=k1; l=i; } k1=-1; } k1++; i++; } cout << k2 << endl << l << endl; } 15.Оставить в строке по одному пробелу между словами. void f(charB []) { intcuri = 0, curn = 0, count = 0; int A[128]; while (B[curi - 1] != 0){ if (B[curi]==32) curn++; elseif (curn> 1) { A[curi - curn] = curn; count++; inti = curi-curn; while (B[i]) { B[i] = B[i + curn - 1]; i++; } curn = 0; curi -= curn; } curi++; } } 16. Возвратить индекс начала фрагмента, симметричного относительно центрального символа (например, "abcba"), и имеющего максимальную длину. Длину фрагмента возвратить по ссылке. 17. "Перевернуть" в строке все слова. (Например: "Жили были дед и баба" - "илиЖилиб дед и абаб"). void f(charB[]) { char temp[256]; intcuri = 0, curn = 0, count = 0; while (B[curi - 1] != 0){ if (isalnum(B[curi])) curn++; elseif (curn> 0) { for (int j = 0, t = curi-1; j temp[j] = B[t]; for (int j = curi-curn,t=0; j B[j] = temp[t]; count++; curn = 0; } curi++; } } 18. Преобразовать целое из внутренней формы во внешнюю в шестнадцатеричной СС. void f(charB[], intx) { int A[10], temp = 0, n = 0; char tem [15]; temp = x; for (int t = temp; t != 0; n++, t /= 10); for (int j = n-1, ch = temp; j+1 > 0; j--) { A[j] = ch % 10; ch /= 10; } inti = 0; for (; i< n; i++) { if (A[i] <= 9) { B[i] = A[i] + '0'; } elseB[i] = A[i] - 10 + 'A'; } } 19. Преобразовать число в шестнадцатеричной СС из внешней формы во внутреннюю. void f(charB[],intC[],intn) { int A[10]; inti = 0; for (; i { if (B[i] >= '0'&&B[i] <= '9') C[i] = B[i] - '0'; elseif (B[i] >= 'A'&&B[i] <= 'F') { C[i] = B[i] - 'A' + 10; } } } 20. Преобразовать дробную часть переменной типа double во внешнюю форму представления (строку символов). 21. В строке находится символ “точка” и символы-цифры дробной части числа. Преобразовать во внутреннюю форму представления (переменную типа double). 22. Найти в строке два одинаковых фрагмента, не содержащих пробелы и имеющих максимальную длину и возвратить индекс начала первого из них. 23. В строке, содержащей абзац текста, найти концы предложений, обозначенный символом "точка". В следующих за ними словах первую строчную букву заменить на прописную. Между словами количество пробелов может быть любым. 24. Заменить в строке все восьмеричные целые константы на символы с соответствующими кодами, (например, 101 на A). 25. Найти слово, начинающееся с самой младшей латинской буквы и возвратить индекс его начала. 26.Удалить из строки комментарии вида "/* ... */". Игнорировать вложенные комментарии. void f(charc []) { int k = 0; for (inti = 0; i { if (c[i] == '/'&&c[i + 1] == '*'&&k==0) { k+=1; c[i] = ' '; c[i + 1] = ' '; } if (c[i] == '/'&&c[i - 1] == '*'&&k == 1) { c[i] = ' '; c[i - 1] = ' '; k = 0; } } } 27. Заменить в строке все большие латинские буквы на соответствующие им шестнадцатеричные коды (например, А на 0x41, в константе использовать 2 цифры для представления байта). 28. Заменить в строке все целые константы из 1-2 цифр соответствующим повторением следующего за ними символа (например "abc5xacb15y" - " abcxxxxxacbyyyyyyyyyyyyyyy "). int f(charB[]) { int s = 0, curn = 0, c = 0, maxcurn = 0; int A[128]; for (inti = 0; i { if (B[i] == B[i + 1]) curn++; elseif (curn>1) { A[i - curn] = curn; if (curn>maxcurn) { maxcurn = curn; c = i - maxcurn; } int temp = curn; if (temp / 10 >= 1) { B[c] = temp % 10 + '0'; temp /= 10; B[c-1] = temp % 10 + '0'; for (inti = c + 3; i B[i] = B[i + maxcurn]; } elseif (temp / 10 == 0) { B[c+1] = temp + '0'; for (inti = c+2; i B[i] = B[i + maxcurn+1]; } curn = 0; } } returnstrlen(B)-2; } 29. Найти в строке и удалить из нее последовательность повторяющихся символов максимальной длины (например, "abcxxxxxacbyyyyyyyyyyyyyyyz" - "abcxxxxxacbz"). int f(charB[]) { int s = 0, curn = 0, c = 0, maxcurn = 0; int A[128]; for (inti = 0; i { if (B[i] == B[i + 1]) curn++; elseif (curn>1) { A[i - curn] = curn; if (curn>maxcurn) { maxcurn = curn; c = i - maxcurn; } curn = 0; } } for (inti = c; i B[i] = B[i + maxcurn+1]; returnstrlen(B); } 30. Найти в строке наиболее часто встречающийся символ и заменить его на пробел. 31. Найти все вхождения подстроки в строке. Строка и подстрока заданы в массивах символов. Результат – массив, заполненный индексами начала подстроки в строке, последовательность ограниченна -1. 32. Найти в строке самую внутреннюю пару скобок и возвратить индекс открывающейся, например “a(bb(c(d)e(f ( ggg)h)))(d)”. 33. Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы до конца массива сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.
34. Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы массива сдвигаются на один влево. Сам элемент переносится в новый массив. 35. Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем на его место записывается «очень большое число», например, максимальное +1. Сам элемент переносится в новый массив. 36. Сортировка выбором. Выбирается максимальный элемент из оставшихся и меняется с последним из них (обратить внимание на диапазон неупорядоченной части). void F36(int A[], int n){ bool op; int i, j, max = 0, pos, curmax = INT_MAX; for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ if (A[j] > A[i]){ if (A[j] > max && A[j] < curmax){ max = A[j]; pos = j; op = true; } } else{ if (A[j] > max && A[j] < curmax){ max = A[j]; pos = j; op = true; } } } curmax = max; max = 0; if (op){ A[pos] = A[n - 1 - i]; A[n - 1 - i] = curmax; op = false; } } } 37. Сортировка выбором. Выбирается минимальный элемент из оставшихся и меняется с первым из них (обратить внимание на диапазон неупорядоченной части). 38.Сортировка подсчетом. Выходной массив заполняется значениями “-1”. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений “-1”. После чего оставшиеся в выходном массиве позиции со значением “-1” заполняются копией предыдущего значения. void f(intA[],intB[],intn) { inti, k, j; for (i = 0; i<= n; i++) B[i] = -1; // Выходной массив заполняется значениями “-1”. for (i = 0; i { k = 0; for (j = 0; j { if (A[j] k = k++; // выходном массиве путем подсчета количества // элементов строго меньших данного } B[k] = A[i]; // присваивает значение элементу массива b } for (i = 1; i { if (B[i] == -1) // значением «-1» заполняется копией предыдущего B[i] = B[i - 1]; // значения } } 39. Сортировка вставками. Берется очередной элемент и извлекается из массива. Затем от начала массива ищется первый элемент, больший данного. Все элементы, от найденного до очередного сдвигаются на один вправо и на освободившееся место помещается очередной элемент. (Поиск места включения от начала упорядоченной части). 40. Сортировка вставками («всплытием»). Берется предпоследний элемент и меняется со следующим, пока не закончится массив и пока следующий будет меньше текущего. Затем берется предыдущий и т.д.. 41. Сортировка вставками. Берется очередной элемент массива. Затем от начала выходного массива ищется первый элемент, больший данного. Все элементы, от найденного до последнего сдвигаются на один вправо и на освободившееся место помещается очередной элемент. 42. Сортировка выбором. Выбирается минимальный элемент в массиве и переносится в новый массив. Затем на его место записывается последний элемент исходного массива. |