昨天，由于比賽嚴禁在5月31日當天通過任何渠道傳播、討論題目、解答方法和程序。網易“有道難題”打電話，特別聲明，讓我暫時刪掉關于這兩道算法的隨筆，哈哈，嚇我一跳，我差點泄題，不過遵循她意見后，將昨天的帖子刪掉，改到今天拿出來一起切磋一下。程序競賽之所以吸引眾多編程愛好者，是因為可以再互相學習、切磋提高。:)
摘要
昨天，由于比賽嚴禁在5月31日當天通過任何渠道傳播、討論題目、解答方法和程序。網易“有道難題”打電話，特別聲明，讓我暫時刪掉關于這兩道算法的隨筆，哈哈，嚇我一跳，我差點泄題，不過遵循她意見后，將昨天的帖子刪掉，改到今天拿出來一起切磋一下。程序競賽之所以吸引眾多編程愛好者，是因為可以再互相學習、切磋提高。:)
第一道算法題（250分）
話說你在走路上班時，經過一片種植蘿卜的農田。這塊田地的形狀是一個矩形的網格。field的第i個元素的第j個字符，表示田地的第i行第j列的格子里包含的蘿卜的數目。我們定義一個格子的特殊程度為它周圍所有格子的蘿卜個數的和; 它周圍的格子包含它上下左右以及對角相鄰的格子，最多有8個，在田地的邊界上的格子會少一些。如果一個格子周圍沒有別的格子，則它的特殊程度為0。
請返回田地中特殊程度在A和B之間的所有格子的數目（包含A,B）。
Definition
Class: NumberField
Method: countSpecialNumbers
Parameters: string[], int, int
Returns: int
Method signature: int countSpecialNumbers(string[] field, int A, int B)
(be sure your method is public)
Constraints
- field 包含1個到50個元素，含1和50。
- field的每個元素包含1個到50個字符，含1和50。
- field的每個元素包含相同的字符數。
- field的每個元素的字符均為’0’到’9’之一。
- A的范圍會在0到100之間，含0和100。
- B 的范圍會在A到100之間，含A和100。
Examples
0)
{"111",
"111",
"111"}
4
8
Returns: 5
在這塊田地里面，位于角落的格子的特殊程度是3，位于中間的格子的特殊程度是8，其他4個格子的特殊程度為5。
1)
{"111",
"141",
"111"}
4
8
Returns: 9
現在所有的9個格子都滿足要求。
2)
{"2309",
"0239",
"2314"}
5
7
Returns: 3
3)
{"924",
"231",
"390",
"910",
"121"}
31
36
Returns: 0
4)
{"5"}
3
8
Returns: 0
5)
{"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890",
"1234567890"}
3
18
Returns: 26
以下是我實現的用一個方法搞定的代碼:
C#代碼實現一
/// <summary>
/// 蘿卜地
/// </summary>
/// <param name="field">矩陣</param>
/// <param name="A">范圍A</param>
/// <param name="B">范圍B</param>
/// <returns></returns>
/// <author>周利華(http://www.zivsoft.com)</author>
public int countSpecialNumbers(string[] field, int A, int B)
{
int i = 0, j = 0, result = 0, v = 0;
if (field == null || field.Length == 0) return result;//無方格
int xLen = field.Length, yLen = field[0].Length;//列，行長度
for (i = 0; i < xLen; i++)
{
for (j = 0; j < yLen; j++)
{
if (i + 1 < xLen && j - 1 > -1) v += Convert.ToInt32(field[i + 1][j - 1].ToString());//右上
if (i + 1 < xLen) v += Convert.ToInt32(field[i + 1][j].ToString());//右中
if (i + 1 < xLen && j + 1 < yLen) v += Convert.ToInt32(field[i + 1][j + 1].ToString());//右下
if (i - 1 > -1 && j - 1 > -1) v += Convert.ToInt32(field[i - 1][j - 1].ToString());//左上
if (i - 1 > -1) v += Convert.ToInt32(field[i - 1][j].ToString());//左中
if (i - 1 > -1 && j + 1 < yLen) v += Convert.ToInt32(field[i - 1][j + 1].ToString());//左下
if (j - 1 > -1) v += Convert.ToInt32(field[i][j - 1].ToString());//中上
if (j + 1 < yLen) v += Convert.ToInt32(field[i][j + 1].ToString());//中下
if ((v > A || v == A) && (v == B || v < B)) result++;//找到一個滿足要求的答案
v = 0;//清零
}
}
return result;
}下面的實現由西狐.Net提供，原文：http://www.rzrgm.cn/hooyes/archive/2009/06/01/radish.html
C#代碼實現二
/// <summary>
/// 獲取第i,j格的蘿卜數
/// </summary>
/// <param name="i">行</param>
/// <param name="j">列</param>
/// <param name="field"></param>
/// <returns></returns>
private int GetRadishNumber(int i, int j, string[] field)
{
if (i < 0 || j < 0) return 0;
if ((i > field.Length-1) || (j > field[0].Length-1)) return 0;
return Convert.ToInt32(((char)Encoding.ASCII.GetBytes(field[i])[j]).ToString());
}
/// <summary>
/// 獲取第i,j格的特殊程度
/// </summary>
/// <param name="i">行</param>
/// <param name="j">列</param>
/// <param name="field">矩陣</param>
/// <returns></returns>
private int GetSpecialValue(int i, int j, string[] field)
{
return GetRadishNumber(i - 1, j, field) + GetRadishNumber(i + 1, j, field) + GetRadishNumber(i, j - 1, field) + GetRadishNumber(i, j + 1, field) + GetRadishNumber(i - 1, j - 1, field) + GetRadishNumber(i + 1, j + 1, field) + GetRadishNumber(i - 1, j + 1, field) + GetRadishNumber(i + 1, j - 1, field);
}
/// <summary>
/// 返回滿足特殊度在A至B之間的格子數
/// </summary>
/// <param name="field"></param>
/// <param name="A">特殊度下限</param>
/// <param name="B">特殊度上限</param>
/// <returns></returns>
public int countSpecialNumbers(string[] field, int A, int B)
{
int iResult = 0;
if (field == null || field.Length == 0) return iResult;
int y = field.Length - 1; //行
int x = field[0].Length - 1; //列
for (int i = 0; i <= y; i++)
{
for (int j = 0; j <= x; j++)
{
int tInt = GetSpecialValue(i, j, field);
if (tInt >= A && tInt <= B)
{
iResult++;
}
}
}
return iResult;
}
對于題目一，做完后，總感覺這是不是在考“動態規劃”的算法思想？雖然如此，但我個人認為是不是需要考慮動態規劃的方法來優化，感覺有重復的計算“特殊程度”。但由于只是讀數據，所以沒做動態規劃方面的修改。:-)
第二道算法題（500分）
題目要求：雙倍超立方數是指一個正整數可以正好被拆分為兩種不同的a^3+b^3的方式，其中a,b均為整數且0<a<=b。對于任何一個指定的 int n, 返回所有的小于等于n的雙倍超立方數的個數。
Definition
Class: TwiceSuperCubic
Method: count
Parameters: int
Returns: int
Method signature: int count(int n)
(be sure your method is public)
Constraints
- n取值范圍為1到1,000,000,000(含)
Examples
0)
1
Returns: 0
1)
1729
Returns: 1
1729=1^3+12^3
1729=9^3+10^3
2)
475574
Returns: 27
C#代碼實現
public int count(int n)
{
int a, b;
int up = (int)Math.Pow((double)n / 2, 1f / 3);
int down = (int)Math.Pow((double)n, 1f / 3);
int count = 0;
int[][] matrix=new int[up+1][];
for (int i = 1; i <= up; i++)
{
matrix[i] = new int[down + 1];
}
for (a = 1; a <= up; a++)
{
for (b = a; b <= down; b++)
{
matrix[a][b] = a * a * a + b * b * b;
}
}
for (a = 1; a < up; a++)
{
for (b = a; b <= down; b++)
{
for (int c = a + 1; c <= up; c++)
{
for (int d = c; d <= down; d++)
{
if (matrix[a][b] == matrix[c][d] && matrix[a][b] <= n) count++;
else if (matrix[a][b] < matrix[c][d]) break;
}
}
}
}
return count;
}
作者：周利華
出處：http://www.rzrgm.cn/architect/archive/2009/06/01/1493519.html
本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。
浙公網安備 33010602011771號