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

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

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

не совсемм понимаю как мне надо сравнивать,что больше :
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++
Обратный порядок.. C++
C++ Порядок перестановок
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
11.01.2012, 12:45     Лексикографический порядок #2
ЛеЖиК), очень ёмкая информация... тут же все кинулись искать эту задачу и читать что это числа или строки, и что такое лексикографическое возрастание.
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
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
инженер-системотехник
 Аватар для 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
Сообщений: 630
12.01.2012, 11:29  [ТС]     Лексикографический порядок #5
спасибо
а такой примерчик
999 0123
Haster
инженер-системотехник
 Аватар для Haster
109 / 108 / 2
Регистрация: 10.03.2009
Сообщений: 533
12.01.2012, 11:51     Лексикографический порядок #6
999 > 0123
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
12.01.2012, 17:07     Лексикографический порядок #7
ЛеЖиК), вообще не понимаю связи между первым постой и задачей. Тебе надо вычислить 2012 знаков после точки в числе Пи и выдать результат смещенный на 64 элемента влево, а проще сместить указатель вправо и выдать результат.
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
12.01.2012, 17:37  [ТС]     Лексикографический порядок #8
alkagolik, я по другому понял задание
мне нужно получить массив из 2012 элементов.
В каждом элементе будет n( 2012,2011...1,0) последних символов из первых 2012 символов числа пи
Потом отсортировать его по лексикографическому возрастанию
и вывесть 64 элемент
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
12.01.2012, 17:41     Лексикографический порядок #9
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
Рассмотрим строку длиной 2012, полученную как запись 2012 знаков числа pi после десятичной точки (начинающуюся с "1415..."). Какая строка будет находиться в элементе массива с индексом 64? Элементы массива нумеруются от 0
есть вопрос и на него надо ответить. Вроде все очевидно. Смотри библиотеку gmp, там есть вычисление чисел после точки в числе Пи
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
12.01.2012, 17:50  [ТС]     Лексикографический порядок #10
Цитата Сообщение от alkagolik Посмотреть сообщение
Смотри библиотеку gmp, там есть вычисление чисел после точки в числе Пи
да пригодиться


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



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

и так бы было слишком просто для олимпиадной задачи
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
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++
 Аватар для Thinker
4215 / 2189 / 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
Сообщений: 630
13.01.2012, 16:30  [ТС]     Лексикографический порядок #13
Thinker, да согласен с вами, буду делать так же

alkagolik, в нашем споре хотелось бы услышать кого-нибудь третьего.
Мне все же кажется что я прав, а аргумант
Цитата Сообщение от alkagolik Посмотреть сообщение
ну ну, успехов
неубидителен)
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
13.01.2012, 16:52     Лексикографический порядок #14
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
неубидителен)
я не убеждаю, а желаю удачи. Вы же так и не прилепили к посту файл с 2012 символами после точки в числе Пи.
Сейчас я понимаю задачу так. Есть строка s длиной 2012 байт + 0 ( где она ? ), есть длина суффикса ( где она? ), надо сформировать матрицу размерности [ s/n ] x [ n ] и отсортировать ее в лексикографическом порядке, ( или отсортировать строку а уже потом формировать матрицу? ). Вы же так ничего и не объяснили что вам надо. Вопрос (риторический): для чего вам нужна эта олимпиада?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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);
}
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
13.01.2012, 23:17  [ТС]     Лексикографический порядок #16
diagon, такой же код, только не знал функцию сорт и писал ее вручную, и наполнение вектора чуть по другому

Добавлено через 58 минут
ответ получился довольно длинный
у тебя
такой?
03526193118817101000313783875288658753320838142061717766914730359825349042875546
87311595628638823537875937519577818577805321712268066130019278766111959092164201
98938095257201065485863278865936153381827968230301952035301852968995773622599413
89124972177528347913151557485724245415069595082953311686172785588907509838175463
74649393192550604009277016711390098488240128583616035637076601047101819429555961
98946767837449448255379774726847104047534646208046684259069491293313677028989152
10475216205696602405803815019351125338243003558764024749647326391419927260426992
27967823547816360093417216412199245863150302861829745557067498385054945885869269
95690927210797509302955321165344987202755960236480665499119881834797753566369807
42654252786255181841757467289097777279380008164706001614524919217321721477235014
14419735685481613611573525521334757418494684385233239073941433345477624168625189
83569485562099219222184272550254256887671790494601653466804988627232791786085784
38382796797668145410095388378636095068006422512520511739298489608412848862694560
42419652850222106611863067442786220391949450471237137869609563643719172874677646
575739624138908658326459958133904780275900994657640789512
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.01.2012, 09:53     Лексикографический порядок #17
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
diagon, такой же код, только не знал функцию сорт и писал ее вручную, и наполнение вектора чуть по другому

Добавлено через 58 минут
ответ получился довольно длинный
у тебя
такой?
03526193118817101000313783875288658753320838142061717766914730359825349042875546
87311595628638823537875937519577818577805321712268066130019278766111959092164201
98938095257201065485863278865936153381827968230301952035301852968995773622599413
89124972177528347913151557485724245415069595082953311686172785588907509838175463
74649393192550604009277016711390098488240128583616035637076601047101819429555961
98946767837449448255379774726847104047534646208046684259069491293313677028989152
10475216205696602405803815019351125338243003558764024749647326391419927260426992
27967823547816360093417216412199245863150302861829745557067498385054945885869269
95690927210797509302955321165344987202755960236480665499119881834797753566369807
42654252786255181841757467289097777279380008164706001614524919217321721477235014
14419735685481613611573525521334757418494684385233239073941433345477624168625189
83569485562099219222184272550254256887671790494601653466804988627232791786085784
38382796797668145410095388378636095068006422512520511739298489608412848862694560
42419652850222106611863067442786220391949450471237137869609563643719172874677646
575739624138908658326459958133904780275900994657640789512
Нет,
другой
034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151557485724245415069595082953311686172785588907509838175463746493931925506040092770167113900984882401285836160356370766010471018194295559619894676783744944825537977472684710404753464620804668425906949129331367702898915210475216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992458631503028618297455570674983850549458858692699569092721079750930295532116534498720275596023648066549911988183479775356636980742654252786255181841757467289097777279380008164706001614524919217321721477235014144197356854816136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179049460165346680498862723279178608578438382796797668145410095388378636095068006422512520511739298489608412848862694560424196528502221066118630674427862203919494504712371378696095636437191728746776465757396241389086583264599581339047802759009946576407895
.
Все-таки я напишу вычисление пи, но уже на java, на всякий случай. На плюсах дробную длинную арифметику как-то не комильфо писать.
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
14.01.2012, 13:37  [ТС]     Лексикографический порядок #18
жалко с java я не знаком
странно, правельно в конце ответа должно быть 95, буду искать ошибку у себя

Добавлено через 13 минут
у меня начальное пи другое
я брал егоздесь
а ты откуда
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
14.01.2012, 13:42     Лексикографический порядок #19
Цитата Сообщение от ЛеЖиК) Посмотреть сообщение
жалко с java я не знаком
странно, правельно в конце ответа должно быть 95, буду искать ошибку у себя
Добавлено через 13 минут
у меня начальное пи другое
я брал егоздесь
а ты откуда
Где-то в интернете нашел.
Сейчас на java переписал, там такой же ответ получился.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2012, 13:44     Лексикографический порядок
Еще ссылки по теме:

C++ Шахматный порядок
Обратный порядок С++ C++
Порядок даты C++

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

Или воспользуйтесь поиском по форуму:
ЛеЖиК)
 Аватар для ЛеЖиК)
157 / 60 / 1
Регистрация: 29.04.2011
Сообщений: 630
14.01.2012, 13:44  [ТС]     Лексикографический порядок #20
хорошо
спасибо
Yandex
Объявления
14.01.2012, 13:44     Лексикографический порядок
Ответ Создать тему
Опции темы

Текущее время: 02:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru