Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.66
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
#1

Лексикографический порядок - C++

11.01.2012, 12:42. Просмотров 4381. Ответов 19
Метки нет (Все метки)

в задаче попалась фраза : отсортировать массив в порядке лексографического возрастания

не совсемм понимаю как мне надо сравнивать,что больше :
123 и 999
1230 и 999
1234 и 999
1234 и 9990
4321 и 1234

напишите пожалуста результаты сравнения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.01.2012, 12:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Лексикографический порядок (C++):

Лексикографический порядок для строк - C++
Помогите пожалуйста! Буду рад, любым советам(желательно с приведённым кодом), как и любой новичок. Нужно получить такие перестановки строк:...

Порядок отрицательных членов изменить на обратный, порядок неотрицательных сохранить - C++
Задача (нужно все 3 пункта в 1 программе сделать) Прошу Помочь В условиях задания 3 а) порядок отрицательных членов изменить на...

Шахматный порядок - C++
Привет всем :) Есть код. Нужно чтобы знак "*" выводился в шахматном порядке( смотрите вложение ). Заранее спасибо :) #include...

Обратный порядок - C++
Дан массив размера N. Переставить в обратном порядке элементы массива, расположенные между его минимальным и максимальным элементами,...

Обратный порядок С++ - C++
Добрый вечер. Есть прога, но не могу разобраться в ней, можете поставить комментарии? И как реализовать этот же код программы, но что бы...

Порядок препроцессоров - C++
Возникла проблема с очерёдностью препроцессоров, где в 1ом случае компилятор не "видит" #define _USE_MATH_DEFINES, который определён ниже...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alkagolik
Заблокирован
11.01.2012, 12:45 #2
ЛеЖиК), очень ёмкая информация... тут же все кинулись искать эту задачу и читать что это числа или строки, и что такое лексикографическое возрастание.
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
11.01.2012, 13:05  [ТС] #3
Википедия

а вот сама задача, но думаю она не очень сложная, главное узнать как этот порядок работает
Задание 7. Пусть дана строка s длины n. Суффиксом sn строки s является строка, образованная из последних n символов строки s. Таким образом, sn совпадает с s, а s0 – это пустая строка. Все n + 1 суффиксов строки s можно поместить в массив и отсортировать массив в порядке лексикографического возрастания. Такой массив называется суффиксным массивом . Рассмотрим строку длиной 2012, полученную как запись 2012 знаков числа pi после десятичной точки (начинающуюся с "1415..."). Какая строка будет находиться в элементе массива с индексом 64? Элементы массива нумеруются от 0
Haster
инженер-системотехник
109 / 108 / 2
Регистрация: 10.03.2009
Сообщений: 533
11.01.2012, 17:46 #4
Если я правильно понял, то так:
123 < 999
1230 > 999
1234 > 999
1234 < 9990
4321 > 1234

Хотя мозг плавится )))
Вроде как для натуральных чисел естественный порядок сравнения
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
12.01.2012, 11:29  [ТС] #5
спасибо
а такой примерчик
999 0123
Haster
инженер-системотехник
109 / 108 / 2
Регистрация: 10.03.2009
Сообщений: 533
12.01.2012, 11:51 #6
999 > 0123
alkagolik
Заблокирован
12.01.2012, 17:07 #7
ЛеЖиК), вообще не понимаю связи между первым постой и задачей. Тебе надо вычислить 2012 знаков после точки в числе Пи и выдать результат смещенный на 64 элемента влево, а проще сместить указатель вправо и выдать результат.
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
12.01.2012, 17:37  [ТС] #8
alkagolik, я по другому понял задание
мне нужно получить массив из 2012 элементов.
В каждом элементе будет n( 2012,2011...1,0) последних символов из первых 2012 символов числа пи
Потом отсортировать его по лексикографическому возрастанию
и вывесть 64 элемент
alkagolik
Заблокирован
12.01.2012, 17:41 #9
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
Рассмотрим строку длиной 2012, полученную как запись 2012 знаков числа pi после десятичной точки (начинающуюся с "1415..."). Какая строка будет находиться в элементе массива с индексом 64? Элементы массива нумеруются от 0
есть вопрос и на него надо ответить. Вроде все очевидно. Смотри библиотеку gmp, там есть вычисление чисел после точки в числе Пи
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
12.01.2012, 17:50  [ТС] #10
Цитата Сообщение от alkagolik Посмотреть сообщение
Смотри библиотеку gmp, там есть вычисление чисел после точки в числе Пи
да пригодиться


Цитата Сообщение от alkagolik Посмотреть сообщение
есть вопрос и на него надо ответить.
да но зачем тогда давался предыдуший текст задачи



Цитата Сообщение от alkagolik Посмотреть сообщение
Какая строка будет находиться в элементе
и вопрос именно какая строка а не какой символ

и так бы было слишком просто для олимпиадной задачи
alkagolik
Заблокирован
12.01.2012, 18:06 #11
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
да но зачем тогда давался предыдуший текст задачи
это точность вычислений. т.е. то что после 2012 элемента после точки нам уже не важно.
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
и вопрос именно какая строка а не какой символ
C
1
2
3
4
5
6
char *p = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
++p; ++p;
char *point = p;
printf( "%s", point );
point = point + 64;
printf( "%s", point );
Добавлено через 1 минуту
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
и так бы было слишком просто для олимпиадной задачи
ну ну, успехов
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.01.2012, 20:07 #12
Цитата Сообщение от Haster Посмотреть сообщение
Если я правильно понял, то так:
123 < 999
1230 > 999
1234 > 999
1234 < 9990
4321 > 1234

Хотя мозг плавится )))
Вроде как для натуральных чисел естественный порядок сравнения
Нет. Лексикографический порядок и порядок натуральных чисел - разные вещи. Во первых, любое натуральное число можно представить в разной системе, можно их вообще палочками обозначать или стульями, столами и т.д. (можете посмотреть определение натуральных чисел). При этом
11 > 2 как числа,
но
11 < 2 лексикографически как изображения целых чисел в десятичной системе счисления.
ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 631
13.01.2012, 16:30  [ТС] #13
Thinker, да согласен с вами, буду делать так же

alkagolik, в нашем споре хотелось бы услышать кого-нибудь третьего.
Мне все же кажется что я прав, а аргумант
Цитата Сообщение от alkagolik Посмотреть сообщение
ну ну, успехов
неубидителен)
alkagolik
Заблокирован
13.01.2012, 16:52 #14
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
неубидителен)
я не убеждаю, а желаю удачи. Вы же так и не прилепили к посту файл с 2012 символами после точки в числе Пи.
Сейчас я понимаю задачу так. Есть строка s длиной 2012 байт + 0 ( где она ? ), есть длина суффикса ( где она? ), надо сформировать матрицу размерности [ s/n ] x [ n ] и отсортировать ее в лексикографическом порядке, ( или отсортировать строку а уже потом формировать матрицу? ). Вы же так ничего и не объяснили что вам надо. Вопрос (риторический): для чего вам нужна эта олимпиада?
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.01.2012, 21:49 #15
А я так сделал. Не факт, что правильно.
P.S. то, что пи нужно вычислять вручную, вроде не оговорено.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
const std::string PI = "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151557485724245415069595082953311686172785588907509838175463746493931925506040092770167113900984882401285836160356370766010471018194295559619894676783744944825537977472684710404753464620804668425906949129331367702898915210475216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992458631503028618297455570674983850549458858692699569092721079750930295532116534498720275596023648066549911988183479775356636980742654252786255181841757467289097777279380008164706001614524919217321721477235014144197356854816136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179049460165346680498862723279178608578438382796797668145410095388378636095068006422512520511739298489608412848862694560424196528502221066118630674427862203919494504712371378696095636437191728746776465757396241389086583264599581339047802759009946576407895";
 
int main()
{
    std::vector< std::string > suff(2012 + 1);
    
    for (int i = 0; i < 2013; ++i)
        suff.at(i) = PI.substr( PI.size() - i , i );
    
    std::sort( suff.begin(), suff.end() );
    
    std::cout << suff.at(64);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.01.2012, 21:49
Привет! Вот еще темы с ответами:

порядок байтов - C++
Подскажите, пожалуйста, как записать целое число в битовый файл, чтобы на всех машинах оно считывалось бы с одинаковым порядком байт.

Порядок Хедеров - C++
Добрый день, подскажите, как правильно подключать хедеры если имеются, несколько классов, которые использую друг друга. А именно(все...

порядок в выражении - C++
a.x &lt; b.x || a.x == b.x &amp;&amp; a.y &lt; b.y как это понять: как (a.x &lt; b.x || a.x == b.x) &amp;&amp; a.y &lt; b.y или a.x &lt; b.x || (a.x == b.x &amp;&amp; a.y &lt;...

Обратный порядок - C++
Помогите пожалуйста написать программу, которая печатает текст в обратном порядке. Текст заканчивается точкой. Зарание спасибо!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.01.2012, 21:49
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru