C#常见算法面试

liuyans 2017-07-19

展开全文

转载于：C#常见算法面试

一、求以下表达式的值，写出您想到的一种或几种实现方法： 1-2+3-4+……+m

//方法一，通过顺序规律写程序，同时也知道flag标志位的重要性。

[csharp] view plain copy

static int F1(int m)
{
int sum =0;
bool flag =true;
for (int i = 1; i <= m; i++)
{
if (flag) //一次是默认是True，下下也为True
sum += i;
else
sum -= i;
flag = !flag;
}
return sum;
}
//通过奇偶性
static int F2(int m)
{
int sum = 0;
for (int i = 1; i <= m; i++)
{
if (i % 2 >0) //即为奇数
sum += i;
else
sum -= i;
}
return sum;
}

二、有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

[csharp] view plain copy

class Program
{
static void Main(string[] args)
{
//有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？
//分解题目
//条件：四个数字1、2、3、4 ；三位数：百位、十位、个位
//要求：互不相同；无重复数字：每个数字在三位中只出现一次
//结果：多少个？都是多少？
int count = 0; //统计个数
for (int bw = 1; bw <= 4; bw++)
{
for (int sw = 1; sw <= 4; sw++)
{
if (sw!= bw) //很显然，只有百位和十位不同的情况下才能谈个位。
{
for (int gw = 1; gw <= 4; gw++)
{
if (gw != sw && gw != bw) //百位用过的，十位就不能用；百位和十位都用过的，个位就不能用
{
count++;
Console.WriteLine("{0}{1}{2}", bw, sw, gw);
}
}
}
}
}
Console.WriteLine("一共有{0}个", count);
Console.Read();
}
}

三、一个6位数乘以一个3位数，得到一个结果。但不清楚6位数的两个数字是什么，而且结果中有一位数字也不清楚，请编程找出问好代表的数字，答案可能有多个。

表达式：12?56?*123 = 154?4987

[csharp] view plain copy

for (int a = 0; a < 10; a++)
{
for (int b = 0; b < 10; b++)
{
for (int c = 0; c < 10; c++)
{
if ((120560 + a + b * 1000) * 123 == 15404987 + c * 10000)
{
Console.WriteLine(a);
Console.WriteLine(b);
Console.WriteLine(c);
}
}
}
}
Console.Read();

四、1、1、1、2、3、5、8、13、21、34，....用C#递归写出算法，算出第30个数。

[csharp] view plain copy

using System;
class Program
{
static in F(int i)
{
if(i<=0)
return 0;
else if(i>0 && i<=2)
return 1;
else return F(i-1) + F(i-2);
}
static void Main(string[] args)
{
int n = F(30);
Console.WriteLine(n.ToString());
}
}

五、有一个字符串 "I am a good man",设计一个函数,返回 "man good a am I"。

[csharp] view plain copy

static string Reverse()
{
string s = "I am a good man";
string[] arr = s.Split(' ');
string res = "";
for (int i = arr.Length - 1; i >= 0; i--)
{
res += arr[i];
if (i > 0)
res += " ";
}
return res;
}

六、C# 九九乘法表算法实现：

[csharp] view plain copy

static void Mu()
{
string t = string.Empty;
for (int i = 1; i < 10; i++)
{
for (int j = 1; j <= i; j++)
{
t = string.Format("{0}*{1}={2} ", j, i, (j * i));
Console.Write(t);
//if (j * i < 82)
// Console.Write(" ");
if (i == j)
Console.Write("\n");
}
}
}

七、在1~10000的整数中，找出同时符合以下条件的数：a.必须是质数。b.该数字各位数字之和为偶数，如数字12345，各位数字之和为1+2+3+4+5=15，不是偶数。

本题考了两个地方：

（1）、质数的理解：质数就是所有比1大的整数中，除了1和它本身外，不再有别的约数。2是一个不是奇数的质数，它既是质数也是偶数，面试者极容易忽略这点。判断数N是否为质数要直接从3开始判断（如果N不是2），首先不能是偶数，然后再判断是否能被3、5、7....整除，直到sqrt(N)止。

（2）、求各位数字之和，可以通过循环取余的办法。

[csharp] view plain copy

using System;
using System.Collections.Generic;
class program
{
static void Mian(string[] args)
{
int N =1000;
List<int> primes = new List<int>();
primes.Add(2);
Console.Write(2+" ");
for(int i=3;i<N,i+=2)
{
if(!)
}
}
static bool IsDigitSumEven(int n)
{
int sum=0;
while(n>0)
{
sum +=n% 10;
n /=10;
}
return sum%2==0;
}
}

冒泡排序：

[csharp] view plain copy

namespace BubbleSorter
{
class BubbleSorter
{
private static int[] myArray;
private static int arraySize;
public static void Sort(int[] a)
{
myArray = a;
arraySize = myArray.Length;
BubbleSort(myArray);
}
public static void BubbleSort(int[] myArray)
{
for (int i = 0; i < myArray.Length-1; i++) //由于数组的特点，从0开始，但myArray的长度为5，所以需要减1，实际进行了（0~3）4趟循环
{
for (int j =0; j < myArray.Length -1- i; j++) //内层循环的要点是相邻比较。当j=4的时候，就推出循环了
{
if (myArray[j] > myArray[j + 1])
{
Swap(ref myArray[j], ref myArray[j + 1]);
}
}
}
}
private static void Swap(ref int left, ref int right)
{
int temp;
temp = left;
left = right;
right = temp;
}
static void Main(string[] args)
{
int[] a = { 2, 1, 5, 10, 9 };
BubbleSorter.Sort(a);
foreach (int i in a)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}

选择排序：

选择排序是一种简单直观的排序算法。它的工作原理如下。

首先在未排序列中找到最小的元素，存放到排序序列的起始位置。然后，在从剩余未排序元素中继续寻找最小的元素，放到排序序列末尾。以此类推，直到所有元素均排序完毕。

[csharp] view plain copy

class SelectSorter
{
private static int[] myArray;
private static int arraySize;
public static void Sort(int[] a)
{
myArray = a;
arraySize = myArray.Length;
SelectSort(myArray);
}
public static void SelectSort(int[] myArray)
{
int i, j, smallest;
for(i=0;i<myArray.Length-1;i++) //数据起始位置，从0到倒数第二个数据
{
smallest = i; //记录最小数的下标
for (j = i + 1; j < myArray.Length; j++) //在剩下的数据中寻找最小数
{
if (myArray[j] < myArray[smallest]) {
smallest = j; //如果有比它更小的，记录下标
}
}
Swap(ref myArray[i], ref myArray[smallest]); //将最小数据和未排序的第一个数交换
}
}
private static void Swap(ref int left, ref int right)
{
int temp;
temp = left;
left = right;
right = temp;
}
static void Main(string[] args)
{
int[] a = new int[] { 4, 2, 1, 6, 3 };
SelectSorter.Sort(a);
for (int i = 0; i < a.Length; i++)
{
System.Console.WriteLine(a[i]);
}
System.Console.Read();
}
}

程序设计：猫大叫一声，所有的老鼠都开始逃跑，主人被惊醒。

思路：1、构造出Cat、Mouse、Master三个类，并能使程序运行。

2、从Mouse和Master中提取抽象。

3、联动效应，只要执行Cat.Cryed()就可以使老鼠逃跑，主人惊醒。

通过这个例子，可以看出，委托事件的应用是极其面向对象的，或者说很对象化！

[csharp] view plain copy