ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺍﺯ ﺍﻋﺪﺍﺩ ﺩﺍﺭﯾﻢ.ﺩﺭ ﻫﺮ ﻣﺮﺣﻠﻪ میﺗﻮﺍﻥ یکی ﺍﺯ ﺳﻪ ﻋﻤﻠﯿﺎﺕ ﺯﯾﺮ ﺭﺍ ﺭﻭﯼ ﺩﻧﺒﺎﻟﻪ ﺍﻧﺠﺎﻡ ﺩﺍﺩ:
ﺍﺟﺮﺍﯼ ﻫﺮ یک ﺍﺯ ﺩﺳﺘﻮﺭﻫﺎﯼ ﺑﺎﻻ یک ﻭﺍﺣﺪ ﻫﺰﯾﻨﻪ ﺩﺍﺭﺩ. ﻣﺘﻐﯿﺮ size ﺩﺭ ﻫﺮ ﻟﺤﻈﻪ ﺗﻌﺪﺍﺩ ﻋﻀﻮﻫﺎﯼ ﺩﻧﺒﺎﻟﻪ ﺭﺍ ﻧﺸﺎﻥ می دهد. ﺑﺮﺍﯼ ﻣﺜﺎﻝ ﻭقتی ﺩﻧﺒﺎﻟﻪﯼ ⟨۳,۶,۱۰,۱⟩ ﺭﺍ ﺩﺍﺭﯾﻢ، size=۴ ﺍﺳﺖ.
ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ $⟨۱,۲,...,۱۰۰⟩$ ﺭﺍ ﺩﺍﺭﯾﻢ.ﭘﺲ ﺍﺯ ﺍﺟﺮﺍﯼ ﺍلگوریتم ﺯﯾﺮ، ﻣﺠﻤﻮﻉ ﺍﻋﻀﺎﯼ ﺩﻧﺒﺎﻟﻪ ﭼﻪ ﺧﻮﺍﻫﺪ ﺑﻮﺩ؟
ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ
$⟨۰,۱⟩$
ﺭﺍ ﺩﺍﺭﯾﻢ.ﭘﺲ ﺍﺯ ﺍﺟﺮﺍﯼ ﺍلگوریتم ﺯﯾﺮ، عنصر اخر دنباله چه خواهد بود؟
به ازای i از ۱ تا ۱۰ انجام بده:
ﻓﺮﺽ ﮐﻨﯿﺪ ﺩﺭ ﺍﺑﺘﺪﺍ ﺩﻧﺒﺎﻟﻪﯼ $⟨۱⟩$ ﺭﺍ ﺩﺍﺭﯾﻢ و میخواهیم با یک برنامه به دنباله $⟨۱,۲,...,۱۰۰⟩$ برسیم. کمینه هزینه (تعداد اجراهای دستورهای) مورد نیاز چیست؟
راهنمایی
ساخت یک عدد متمایز با اعداد کنونی دنباله به حداقل یک عمل merge نیاز دارد و هر عمل merge تعداد اعداد دنباله را یک واحد کم می کند.