اسفند
۳۰
۱۳۹۱

پاسخ مسابقه تمرینی بیان – جمع زیردنباله ها

صورت سوال جمع زیر دنباله ها:

یک دنباله اعداد به شما داده می‌شود. فرض کنید به ازای هر زیر دنباله پیوسته از این دنباله ، مجموع اعداد زیر دنباله در یک لیست نگهداری شود. از شما خواسته شده است که تعداد اعداد متفاوت در این لیست را بدست آورید.

به عنوان مثال دنباله ‎ ‎ را در نظر بگیرید. این دنباله ‎ زیر دنباله متفاوت دارد: و و و و و که مجموع آنها به ترتیب ‎ و ‎و ‎و ‎و و ‎ می باشد. در نتیجه این لیست عنصر متفاوت دارد.

ورودی مساله:

در سطر اول فایل ورودی یک عدد ‎ ‎ قرار دارد که مشخص کننده ی تعداد تست ها می باشد. در هر کدام از ‎ ‎ تست بعدی یک دنباله شرح داده شده است، به این شکل که ابتدا یک عدد ‎ ‎ مشخص کننده ی تعداد اعضای دنباله و سپس ‎ عدد اعضای دنباله آمده اند‎.

تمام اعداد ورودی بین ‎ ‎ و ‎ قرار دارند.

خروجی مساله:

به ازای هر تست، پاسخ سوال را در یک خط جداگانه چاپ کنید.

ورودی و خروجی مثال:
مثال ورودی مثال خروجی
۲

۳

۳ ۲ ۱

۳

۱ ۱ ۱

۵

۳

 

پاسخ من به این سوال:

صورت سوال واضح است. من برای حل این مسئله از یک ماتریس بالامثلثی که به صورت  پویا ساخته میشود استفاده نمودم. اگر ابتدا مقادیر دنباله را در قطر اصلی ماتریس قرار دهیم با یکبار پیمایش و پرکردن تمام خانه های بالای قطر اصلی میتوانیم به تمام جمع های زیر دنباله ها برسیم. برای مثال ماتریس دنباله ی ‎   ابتدا به شکل زیر ساخته میشود:

سپس مقادیر بالای قطر اصلی از جمع عناصر قطر اصلی به دست می آید. به این ترتیب که مقدار خانه (۱،۲) از جمع مقادیر (۱،۱) و (۲،۲) ، مقدار خانه (۲،۳) از جمع مقادیر (۲،۲) و (۳،۳) و بالاخره مقدار خانه (۱،۳) از جمع مقادیر خانه های (۱،۱) و (۲،۲) و (۳،۳) به دست می آید:

برای دنباله های بزرگتر هم میتوان از این شیوه استفاده نمود. فقط باید دقت نمود که مقادیر تکراری از نتیجه محاسبات حذف شوند. به طور مثال در ماتریس بالا عنصر ۳ دوبار تکرار شده که تنها یکبار آن در محاسبات منظور میشود.

 

 

 

 

 

اشتراک گذاری این مطلب:

نوشته‌های مرتبط

درباره نویسنده

برنامه‌نویس ++‏C/C‏ - برنامه‌نویس سیستم‌های گرافیکی با استفاده از کتابخانه ‏OpenGL - برنامه‌نویس #‏C و ..‏



فرستادن دیدگاه