国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

1049. Counting Ones (30)

2019-11-11 06:48:07
字體:
供稿:網(wǎng)友

1. 原題: https://www.patest.cn/contests/pat-a-PRactise/1049

2. 思路:

題意:輸出從1~N之間的所有整數(shù)中含有1的總個(gè)數(shù)。思路:數(shù)學(xué)邏輯題。需要枚舉,歸納出規(guī)律。不易想出來。首先,從1直接數(shù)的方法有些傻,拋棄掉。那么如何處理呢?不妨站在全局進(jìn)行思考,我們無法準(zhǔn)確知道1會(huì)出現(xiàn)在哪一位。那為何我們不從每一位出現(xiàn)1的次數(shù)進(jìn)行累加不就是總次數(shù)呢。okay, 那么我們需要?dú)w納每一位出現(xiàn)1的次數(shù)是多少。假設(shè)我們現(xiàn)在計(jì)算百位上為1的次數(shù)。比如一個(gè)數(shù)12033.1. 若當(dāng)前位cur = 0, 顯然若百位為1,只與高位有關(guān)。比如 100~199, 1100~1199, 總數(shù)為12*100。即高位*位權(quán)。2. cur = 1, 如12133.顯然除了高位,還與低位有關(guān)。即12100~12133,低位有關(guān)時(shí)的總個(gè)數(shù)為 低位數(shù)+1.3. cur > 1, 如12233. 顯然與低位無關(guān)了,與高位及當(dāng)前位有關(guān),但可以把當(dāng)前位累計(jì)到高位上,即 總個(gè)數(shù)為 (高位+1)*位權(quán)。以上就是一個(gè)規(guī)律的展示。

3. 源碼(已AC):

#include<iostream>using namespace std;int main(void){	//freopen("in.txt", "r", stdin);	int N, sum = 0;	cin >> N;	int wgt = 1;//位權(quán)初始1,表示從個(gè)位開始		while (N / wgt != 0)	{		int left = N / (wgt * 10);//表示高位數(shù)		int cur = N / wgt % 10;//當(dāng)前位值		int right = N % wgt;//低位數(shù)值		if (cur == 0)//三種情況			sum += left * wgt;		else if (cur == 1)			sum += left * wgt + right + 1;		else			sum += (left + 1) * wgt;		wgt *= 10;//位權(quán)增加	}	cout << sum << endl;	return 0;}參考自: http://m.blog.csdn.net/article/details?id=38846057
上一篇:pdf2swf

下一篇:變量要搗鼓清!

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 财经| 和林格尔县| 麻江县| 五莲县| 阳朔县| 韶关市| 贡山| 鄂尔多斯市| 文山县| 芦溪县| 宣武区| 寻乌县| 庆阳市| 石林| 吴堡县| 长葛市| 图们市| 台州市| 蚌埠市| 吴桥县| 进贤县| 潢川县| 威信县| 福海县| 汽车| 大宁县| 宁阳县| 英德市| 新邵县| 昌乐县| 浦县| 华坪县| 宜都市| 朝阳县| 温宿县| 肥东县| 额济纳旗| 页游| 玉门市| 萨嘎县| 临夏县|