• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2009年11月11日星期三 sgu111 sgu112 sgu113 sgu114 sgu115


            本校同學(xué)想要代碼的郵件我
            sgu的數(shù)據(jù)太強(qiáng)了,真是太折磨人了

            sgu115:calendar
                sgu的水題

            sgu114:找中位點(diǎn)
                算法導(dǎo)論Excercise 9.3-9的題目
            看了答案之后我的理解性簡(jiǎn)單證明:

            1.sgu的題目等價(jià)于有n個(gè)點(diǎn),每個(gè)點(diǎn)有一個(gè)人,p個(gè)人的話,可以看作是p個(gè)坐標(biāo)相同的點(diǎn)。
            2.考慮n的節(jié)點(diǎn)個(gè)數(shù)
            設(shè)此時(shí)的左半邊的費(fèi)用和設(shè)為a ,右半邊的費(fèi)用和設(shè)為b
            如果n是偶數(shù)
                設(shè)最優(yōu)解坐標(biāo)為x1,x2
                *假設(shè)最優(yōu)解在n / 2 和 n / 2 + 1兩個(gè)點(diǎn)之間
                    Cost = a + b;
                如果移動(dòng)最優(yōu)解的坐標(biāo),很容易可以證明
                只要坐標(biāo)還在兩個(gè)中位點(diǎn)之間,那么解的值就不變。假設(shè)在兩個(gè)中位點(diǎn)之間左移d個(gè)單位
                    Cost = a - (n/2) * d + b + (n/2) * d
                         = a + b;
                右移同理

                *假設(shè)向左移出了中位點(diǎn)的距離
                    Cost = a - (n/2-1) * d + b + (n/2-1) * d + x2 - x1 + d
                         = a + b + d;

                    如果移動(dòng)超過這兩個(gè)點(diǎn),那么解的值都將變大
            如果n是奇數(shù)
                *設(shè)最優(yōu)解坐標(biāo)為x,最優(yōu)值一定在中位點(diǎn)上。
                此時(shí)Cost = a + b;
               
                *假設(shè)最優(yōu)解左移d個(gè)單位
                此時(shí)Cost = a - (n/2)*d + b + (n/2)*d + d
                         = a + b + x - d
                向右移同理
                所以中位點(diǎn)是最優(yōu)值

            114此題就是多了個(gè)計(jì)數(shù)和排序

            sgu113:素?cái)?shù)
            可以發(fā)現(xiàn),只要求sqrt(1000000000) 個(gè)素?cái)?shù)即可,也就是判斷tmp = m / primes[i]
            判斷tmp是否是素?cái)?shù)即可
            trick是,tmp可能大于sqrt(1000000000)!!

            sgu112:大數(shù)冪

            sgu111:大數(shù)求平方根
            方法很多,大多數(shù)人都是模擬手算開方,我看了半天沒看明白,于是弄了哥迭代法 + java 水過
            稍微有一點(diǎn)猥瑣...
            c++版的求平方根方法

            double eps = 1e-8;
            int main()
            {
                int x,i,j,k;
                while(scanf("%d",&x) == 1) {
                    double r = x; //盡量靠近sqrt(x),這里是為了一個(gè)通解
                    double p = 1;
                    while(p + eps < r) {
                        r = (r + p) / 2;
                        p = x / r;
                    }
                    printf("%f\n",r);
                }
                return 0;
            }

            原版的算法,我改了改
               1. Start with an arbitrary positive start value r (the closer to the square root of x, the better).
               2. Replace r by the average between r and x/r, that is: (r + x/r) / 2 ,
                   (It is sufficient to take an approximate value of the average in order to ensure convergence.)
               3. Repeat step 2 until r and x/r are as close as desired.


            posted on 2009-11-11 23:48 schindlerlee 閱讀(1730) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告

            久久久久亚洲AV无码专区首JN | 亚洲国产视频久久| 久久精品国产亚洲Aⅴ蜜臀色欲| 精品久久久久中文字幕一区| 日本加勒比久久精品| 久久er99热精品一区二区| 一本久久a久久精品综合夜夜| 久久久精品人妻无码专区不卡 | 少妇被又大又粗又爽毛片久久黑人| 久久天天躁狠狠躁夜夜不卡| 色综合久久天天综合| 亚洲中文字幕无码久久2020| 久久97久久97精品免视看| 18禁黄久久久AAA片| 88久久精品无码一区二区毛片| 国产精品久久久久免费a∨| 四虎国产精品免费久久久| 中文国产成人精品久久不卡 | 伊人久久大香线蕉亚洲五月天| 国产高清美女一级a毛片久久w| 国产激情久久久久久熟女老人| 久久精品三级视频| 国产高潮久久免费观看| 国产一区二区三区久久精品| 少妇精品久久久一区二区三区| 麻豆av久久av盛宴av| 久久综合亚洲色HEZYO国产| 国产叼嘿久久精品久久| 久久综合综合久久狠狠狠97色88 | 夜夜亚洲天天久久| 国产成人久久精品激情| 久久久久亚洲AV无码麻豆| 久久婷婷五月综合97色直播| 蜜桃麻豆WWW久久囤产精品| 色综合久久夜色精品国产| 久久久久国产| 日本欧美国产精品第一页久久| 国内精品久久久久久中文字幕| 久久久久四虎国产精品| a级毛片无码兔费真人久久| 久久久久国产视频电影|