Значи имам проблем с една задачка по предмета. Трябва да използвам trie, за записването на ходовете на партии шах в бинарен файл. Имам един входен файл, от който чета всяка партия и друг, в който трябва да записвам актуализирания trie. Това ми се губи, не знам какъв тип трябва да е бинарния файл с актуализирания trie и изобщо работата с бинарни файлове не ми е особено ясна. Дано да съм обяснил достатъчно ясно и съответно да има някой добър човек да помогне. Благодаря!

Някаква насока поне?

Някаква насока поне?

На мен даже не ми стана ясна идеята. Имам малък опит с балансирани дървета, но е много скромен...

Не става въпрос за балансирани дървета. Не знам кое да поясня самата имплементация или какво трябва да направя? Капитане, в теб ми беше надеждата. ;(

Не става въпрос за балансирани дървета. Не знам кое да поясня самата имплементация или какво трябва да направя? Капитане, в теб ми беше надеждата. ;(

Ох, това че не са балансирани е ясно. Тези (поне на пръв поглед) май са точно небалансирани, но не ми е ясно как се слиза по дървото и как мога да го нагодя това слизане за записване на шахматни ходове...

П.П. Чакай, май нещо ми стана ясно (не е сигурно). В това дърво трябва да опишеш всички възможни ходове и след това да запишеш във файла, номерата на възлите в които се появяват.

Или втори вариант. Започваш изграждане на дърво. Ход E2-E4 ти прави един клон от вид: Е, 2, Е, 4. Ако следващия ход е Е7-Е5 имаш възел Е и правиш второ разклонение за 7 и от там надолу т.е. изграждаш дървото динамично от последователните ходове като записваш пак номерата на възлите във файла.

П.П.П. Стана егати и обяснението, но отва е единственото смислено, което мога да измисля

Ох, това че не са балансирани е ясно. Тези (поне на пръв поглед) май са точно небалансирани, но не ми е ясно как се слиза по дървото и как мога да го нагодя това слизане за записване на шахматни ходове...

П.П. Чакай, май нещо ми стана ясно (не е сигурно). В това дърво трябва да опишеш всички възможни ходове и след това да запишеш във файла, номерата на възлите в които се появяват.

Или втори вариант. Започваш изграждане на дърво. Ход E2-E4 ти прави един клон от вид: Е, 2, Е, 4. Ако следващия ход е Е7-Е5 имаш възел Е и правиш второ разклонение за 7 и от там надолу т.е. изграждаш дървото динамично от последователните ходове като записваш пак номерата на възлите във файла.

П.П.П. Стана егати и обяснението, но отва е единственото смислено, което мога да измисля

Самото изграждане на дървото ми е ясно изобщо работата с trie ми е ясна. Просто стъпката към двоичен файл ми се губи. Изобщо записването на подобна структура в двоичен файл не ми е ясна. Програмата така като мисля, трябва да е нещо от сорта.

1. Четене от файла, в който имам trie-я.

2. Четене от файла, в който имам новата партия и добавям ходовете в trie-я.

3. Актуализиране на файла "майка".

Самото изграждане на дървото ми е ясно изобщо работата с trie ми е ясна. Просто стъпката към двоичен файл ми се губи. Изобщо записването на подобна структура в двоичен файл не ми е ясна. Програмата така като мисля, трябва да е нещо от сорта.

1. Четене от файла, в който имам trie-я.

2. Четене от файла, в който имам новата партия и добавям ходовете в trie-я.

3. Актуализиране на файла "майка".

Хм, няма ли да е по-добре така:

1. четем партията и правим дървото

2. намираме максималниия номер на възел (като число)

3. закръгляваме нагоре към нещо 2^x

4. четем файла, мачваме ход в дървото и пишем в друг файл номера на възела във формат 0-(2^x-1)

Редактирано 12 април 201016 г. от capnemo (преглед на промените)

Хм, няма ли да е по-добре така:

1. четем партията и правим дървото

2. намираме максималниия номер на възел (като число)

3. закръгляваме нагоре към нещо 2^x

4. четем файла, мачваме ход в дървото и пишем в друг файл номера на възела във формат 0-(2^x-1)

Не мисля, че разбирам точно идеята ти и ако можеш да започнеш с това с какво е по-добър вариант. Отделно алгоритмите за въвеждане на нов ход, изтриване и за ново дърво трябва да са О(1). Бързодействието и максималното придържане към идеята за trie трябва да са основния критерий.

Не мисля, че разбирам точно идеята ти и ако можеш да започнеш с това с какво е по-добър вариант. Отделно алгоритмите за въвеждане на нов ход, изтриване и за ново дърво трябва да са О(1). Бързодействието и максималното придържане към идеята за trie трябва да са основния критерий.

В началото нямаме никакво дърво, изграждаме го четейки и анализирайки ходовете.

След това отределяме максималното число на номер на възел за да можем да запишем с най-малко битове номера на възел (т.е. ход). Нататък е стандартно.

Ако се гони бързина трябва да създадем дървото и да открием възел на кое ниво е най-широк, т.е. се записва с най-много битове и да приемем това за ширина на записа на един възел. В този случай един ход е последователност от 4 възела. Не знам кое от горните по-точно пасва на идеята на тези дървета, нямам никакъв опит с тях

В началото нямаме никакво дърво, изграждаме го четейки и анализирайки ходовете.

След това отределяме максималното число на номер на възел за да можем да запишем с най-малко битове номера на възел (т.е. ход). Нататък е стандартно.

Ако се гони бързина трябва да създадем дървото и да открием възел на кое ниво е най-широк, т.е. се записва с най-много битове и да приемем това за ширина на записа на един възел. В този случай един ход е последователност от 4 възела. Не знам кое от горните по-точно пасва на идеята на тези дървета, нямам никакъв опит с тях

Благодаря ти много, ще дерзая, да видим.

Благодаря ти много, ще дерзая, да видим.

Искрено се надявам да съм помогнал с нещо