فلسفه ی وجود و یا عدم وجود جفت اعداد مسخره
برنامه نویسی پویا چیست و مسائل مهم آن کدامند؟ (قسمت اول)
سوال one two one two one two...
مشکل در حل سوالات الگوریتم های داینامیک
از ورودی یک عدد به نام s میگریم حال باید از 1 تا 9^10تعداد اعدادی که
مجومع ارقامشان برابر با s می شود را به دست بیاوریم.
به عنوان مثال برای s=1 این تعداد می شود 10. S بین 1 تا 82 هست و تایم لیمیت 1 ثانیه است.
اول یه تابع می دیم که تعداد جواب های معادله زیر رو به دست بیاره: x1+x2+… +xk=s به طوری که 10> xi و xi≥ 0 که با شمول تو اردر دو به توان k حل میشه سپس یه فور رو k از 1 تا 9 می زنیم و سوال حل میشه.
2015-08-31 17:31:42 -0600 شجاعی فر@حسن رستمی پور راس میگی! حواسم نبود s بیشتر از 9*9 باشه جواب میشه ۰! xD
2015-08-31 17:50:36 -0600 توفیقیاینجوری حلش می‌کنیم: $$ dp[i][j]$$ رو برابر تعداد اعداد i رقمی که مجموع ارقام آنها برابر با $j$ هست در نظر بگیر.
$dp[1][i] = 1 (i < 10) $ , $dp[1][i] (i > 9) = 0 $ هست.
حالا اینجوری پر می‌کنیم: $$ dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-9] $$ (روی یکان حالت بندی کردم که ۰ باشه، یک باشه، دو باشه و ... )
جواب مسئله برابر با : $$dp[1][s] + dp[2][s] + dp[3][s] + ... + dp[9][s]$$ هست.
اره دیگه کدشو نوشتم!!! میخوای حالتی که اعداد رو هم بهمون بده بنویسم؟؟
2015-09-01 03:47:04 -0600 حمیدرضا کامکاری(O(slogn متغیر n کران بالای اعداده لگاریتمم در مینای دهه از این اردر پایین تر به روش داینامیک نداریم(مطمئنم)
2015-09-01 03:50:51 -0600 حمیدرضا کامکاریChera mesle arash mahmoudian code mizani? mage badbakhte bichare che gonahi karde ke bayad daste adami mesle to biofte? badesham az oon asr hajar dara noobe badbakht akhe ki esme motaghayerasho "func" mizare
2015-09-01 07:56:04 -0600 خرس بقالسلام. اول یه لم می دیم که با اون سوال خیلی ساده تر حل میشه و نیازی به استفاده از اصل شمول و عدم شمول به طور مستقیم نیست.
لم: تعداد جواب های معادله $ x_1+x_2+...+x_k = n $ در مجموعه اعداد $ {0,1,2,....,r} $ (محموعه اعداد حسابی کوچکتر از $r+1$) از فرمول زیر محاسبه میشه.
$\sum_{j=0}^{k} (-1)^j\binom{k}{j}\binom{n-jr+k-1}{k-1}$
برهان:
برای اثبات ابتدا جزوه زیر رو بخونید. اثبات این لم مشابه برهانی است که برای قضیه 1آورده شده است.
کاربرد هایی از اصل شمول و عدم شمول - داشنامه رشد.
حالا کافیه یه تابع بنویسید که مقدار فرمول بالا رو برای $ k$ و $ r $ دلخواهی محاسبه کنه و با اون تعداد جواب های معادله برای $r=10 $ و k=9$ $ محاسبه کنید
توجه داشته باشید که با این فرمول تعداد همه عددهای حداکثر $k$ رقمی که جمعشون برابر $n$ باشه رو میشه محاسبه کرد.
:||| BEKHODA KHEILI KHARIN. 8 ta for 0-9 bendaz bebin jameshoon s mishe ya na
2015-09-01 07:51:42 -0600 خرس بقال@خرس بقال عزیزم اولا ۸ تا نه ۹ تا for باید بزنی بعدشم اگه اوردرش رو حساب کنی میشه ۱۰ به توان ۹ یعنی اینکه تایم میشه!!لطفا یکم فکر کن بعد نظر بده.!
2015-09-01 08:28:28 -0600 حسن رستمی پورKodan, harfe dahaneto befahm. To hichi bejoz ye noob hasti ke miyay too shalvare ma baad be ma enteghaad vared mikoni?
2015-09-01 10:27:16 -0600 خرس بقال