Ştern-Broko ədədi sistemi
Ştern-Broko ağacı, sadələşdirilməyən kəsrlərin m / n çoxluğunu qurmaq üçün incə bir üsuldur, burada m və n qarşılıqlı sadə ədədlərdir. Bu metod, iki başlanğıc kəsrindən başlayaraq, aşağıda təsvir edilən əməliyyatı təkrarlamaqla həyata keçirilir:
İki qonşu kəsr arasında yeni bir kəsr yerləşdirin.
Məsələn, ilk addımda və arasında bir yeni kəsr əlavə edilir:
Növbəti addımda daha iki kəsr əlavə edilir:
Daha sonra, dörd yeni kəsr əlavə edilir:
Bütün bu proses sonsuz bir ikili ağac kimi təsəvvür edilə bilər və ağacın yuxarı səviyyələri belə görünür:
Bu quruluş sıralamanı qoruyur, belə ki, eyni kəsri müxtəlif yerlərdə əldə edə bilmərik.
Əslində, Ştern-Broko ağacını rasional ədədləri təqdim etmək üçün bir say sistemi kimi düşünə bilərik, çünki hər bir müsbət, sadələşdirilməyən kəsr ağacda yalnız bir dəfə rast gəlinir. Biz L və R hərflərindən istifadə edəcəyik, ağacın kökündən müəyyən bir kəsrə enərkən sol və ya sağ budaq boyunca hərəkət etdiyimizi göstərmək üçün; bu L və R ardıcıllığından ibarət olan bir sıra ağacdakı mövqeyi unikal şəkildə müəyyən edir. Məsələn, LRRL sol budaqdan sağa, sonra sağa, sonra sola getdiyimizi göstərir. Biz LRRL -ni kimi təqdim edə bilərik. İstənilən müsbət kəsr bu şəkildə L və R -dən ibarət unikal bir sıra ilə təqdim olunur.
Yaxşı, demək olar ki, istənilən kəsr. Kəsrə boş sıra uyğun gəlir. Biz onu I ilə işarələyəcəyik, çünki bu 1 -ə bənzəyir və "identity" (vahid) sözünün ilk hərfidir.
Bu məsələdə siz verilmiş müsbət rasional kəsri Ştern-Broko say sistemində təqdim etməlisiniz.
Giriş verilənləri
Bir neçə testdən ibarətdir. Hər bir test iki qarşılıqlı sadə natural ədəd m və n -dən ibarətdir. Sonuncu test iki vahid ehtiva edir və işlənmir.
Çıxış verilənləri
Hər bir test üçün Ştern-Broko say sistemində verilmiş kəsrin təqdimatını ayrıca bir sətirdə çıxarın.