iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 1
0
自我挑戰組

有志者,事竟成。系列 第 1

Day1 - 前言 + 第一題~第五題

前言

請別打我,這篇就是為了獎牌而發的。(說要把獎牌送人....等我另外一邊完賽我會認真處理這邊)
這一篇是寫UVa和Leetcode還有Newcode的題目。
一天最多發五題,而之後另外一邊完賽後,則是看我當天寫完幾題我就發幾題。
無論如何刷題都是必須的,畢竟我的目標還是考研為優先?(到底誰願意一起陪我考清華!)
最近大多都在寫專案,寫Python,但我深知現在如果叫我上機考C++......呵呵,算了吧,手感肯定不對。
(每次在轉換程式碼的時候那種if後到底有沒有括號,是大括還是縮排...他xx的....)

第一題 UVa100

題目描述

考慮以下的演算法:

  1. 輸入 n
  2. 印出 n
  3. 如果 n = 1 結束
  4. 如果 n 是奇數 那麼 n=3n+1
  5. 否則 n=n/2
  6. GOTO 2

例如輸入 22, 得到的數列: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單,但以上的推測是否真實卻無法知>道。然而對所有的n ( 0 < n < 1,000,000 )來說,以上的推測已經被驗證是正確的。
給一個輸入 n ,透過以上的演算法我們可以得到一個數列(1作為結尾)。此數列的長度稱為n的cycle-length。上面提到的例子, 22 的 cycle length為 16.
問題來了:對任2個整數i,j我們想要知道介於i,j(包含i,j)之間的數所產生的數列中最大的 cycle length 是多少。

思維

硬幹,i到j之間會產生的cycle length算出來。選擇最大的即可。

程式碼

#include<iostream>
using namespace std;

int compute(int n)
{
	int cyclelength=1;
	while(n!=1)
	{
		if(n%2==1)
			n=3*n+1;
		else
			n/=2;
		cyclelength++;
	}
	return cyclelength;
}
int main(){
	int start,end;
	while(cin>>start>>end)
	{
		int cyclelength=0,temp;
		if(start<end)
		{
			for(int i=start;i<=end;i++)
			{
				temp=compute(i);
				if(temp>cyclelength)
					cyclelength=compute(i);
			}	
		}
		else
		{
			for(int i=start;i>=end;i--)
			{
				temp=compute(i);
				if(temp>cyclelength)
					cyclelength=compute(i);
			}	
		}
		cout<<start<<" "<<end<<" "<<cyclelength<<endl;
	}
}

第二題 UVa10018

題目描述

把一個數字反轉並相加的方法很簡單:就是把數字反轉並加上原來的數字。假如這個和不是一個迴文(指這個數字從左>到右和從右到左都相同),就一直重複這個程序。舉例說明:

195 開始的數字
591
................
786
687
................
1473
3741
................
5214
4125
................
9339 迴文出現了

在這個例子中,經過了4次相加後得到了迴文9339。幾乎對所有的整數這個方法都會得到迴文,但是也有有趣的例外。>196是第1個用這個方法找不到迴文的數字,然而並沒有證明該迴文不存在。
現在給你一個開始的數字,你的任務就是求出經過多少次相加後,會產生哪一個迴文。對所有的測試資料,你可以假設:1. 都會有1個答案。2. 在1000個相加內都會得到答案。 3. 產生的迴文不會大於4294967295.

思維

硬幹。(我好像寫程式碼都特別直觀)
我們需要把數字反轉過來的reverse(),將數字反轉後先判斷是否相同(回文),如果沒有就繼續進行相加,同時記錄加了幾次,這樣就行。

程式碼

#include<iostream>
using namespace std;
unsigned int reverse(unsigned int zheng){

	unsigned int fang=0;
	while(zheng){	
		fang=fang*10+zheng%10;
		zheng/=10;
	}
	return fang;}

int main()
{
	int test;
	cin>>test;
	while(test--){
		unsigned int number,reverse_number,add=0;
		cin>>number;
		do{	
			number=number+reverse(number);
			add++;
		}while(number!=reverse(number));
		cout<<add<<" "<<number<<endl;
	}
}

第三題 UVa 10035

題目描述

在小學時我們都做過加法的運算,就是把2個整數靠右對齊然後,由右至左一位一位相加。
如果相加的結果大於等於10就有進位(carry)的情況出現。
你的任務就是要判斷2個整數相加時產生了幾次進位的情況。

思維

把兩數依位數相加,且考慮到後一位進位沒,就能解決這個問題。

程式碼

#include<iostream>
using namespace std;

int main()
{
	int n1,n2;
	while(cin>>n1>>n2)
	{
		if(n1==0&&n2==0)
		break;
		
		int carry=0,c=0;
		while(n1!=0||n2!=0)
		{
			if(n1%10+n2%10+c>9)
			{
				carry+=1;
				c=1;
			}
			else
				c=0;
			n1/=10;
			n2/=10;
		}
		if(n1%10+c>9||n2%10+c>9)
			carry+=1;
		if(carry==0)
			cout<<"No carry operation."<<endl;		
		else if(carry==1)
			cout<<"1 carry operation."<<endl;		
		else
			cout<<carry<<" carry operations."<<endl;
	}	
}

第四題 UVa10370

題目描述

據說,90%的大學一年級新生期望他們自己的成績能在全班平均之上,請你來幫忙驗證看看他們有沒有達成目標。
輸入的第一列有一個整數 C 代表以下有多少組測試資料。每組資料的第一個整數 N 代表班級總人數 ( 1 <= N <= 1000 )。接下來有N個以空白或換行來間隔的整數,代表每個學生的期末總成績 ( 0 <= 分數 <= 100 )。
對每組測試資料輸出一列,算出有多少百分比的學生成績比全班平均高,請四捨五入到小數第三位。

思維

先算出班級平均,再將平均以上的同學除以全部同學得到百分比。
比較值得紀錄的是<iomanip>他是用來處理數字格式化很好的工具
其中setprecision()是代表輸出的位數,但如果數字是3.1415926,我們直接使用setprecision(2)他並不是顯示3.14而是3.1。所以如果我們是規定他要顯示的小數位數的話前面要加上fixed

程式碼

#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
	int tc;
	cin>>tc;
	while(tc--)
	{
		int people;
		cin>>people;
		
		int grade[people],sum=0;
		for(int i=0;i<people;i++)
		{
			cin>>grade[i];
			sum+=grade[i];
		}
		float average=(float)sum/people;
		int count=0;
		for(int i=0;i<people;i++)
		{
			if(grade[i]>average)
			count+=1;
		}
		cout<<fixed<<setprecision(3)<<(float)count/people*100<<'%'<<endl;
	}
}

第五題 UVa10420

題目描述

現在要統計n個人,他們的國籍與姓名。
並計算出這n個人中,每個國家佔有多少人。(代表名字是個屁)
輸出時,請依國家名字順序排序。(ABCD)

思維

這題我的寫法....嗯....到現在看還是覺得挺帥的XD
這並不是Lucky cat上一顆星的題目,是我在考cpe時太閒,第一次嘗試用vector的程式。(這程式前沒用過
因為名字並不重要,所以我們建一個vector然後將所有國家名字依序放進去。
放完後直接用<algorithm>sort()進行排序((自動幫我們排好abc,帥爆!
排好後就開始進行數數,數到與前面國家不同就代表前面國家以統計完畢可以輸出了,數到最後一個print出來,這件事也就完結了。

程式碼

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n;
	string nation,name;
	vector<string> infor;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>nation;
		getline(cin,name);
		infor.push_back(nation);
	}
	sort(infor.begin(),infor.end());
	int count;
	string temp="";
	for(int i=0;i<n;i++)
	{
		if(temp!=infor[i])
		{
			if(i!=0)
				cout<<temp<<" "<<count<<endl;
			temp=infor[i];
			count=1;
		}
		else
			count++;
		if(i==n-1)
			cout<<temp<<" "<<count<<endl;
	}
} 

下一篇
Day2 第六題~第十題
系列文
有志者,事竟成。19
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
阿瑜
iT邦研究生 4 級 ‧ 2019-10-08 12:58:11

學習,是自己的事。
努力,也是自己的事。
在這世界上,沒有什麼事情努力後不會有成果。
相信自己,成就自己。

引自 yueh 的 主題說明:
你的這段話 好勵志!!!

在這世界上,沒有什麼事情努力後不會有成果。 推推

我要留言

立即登入留言